[BZOJ 4195] [Noi 2015] 프로그램 자동 분석
http://www.lydsy.com/JudgeOnline/problem.php?id=4195
제목 의 대의
일련의 상등 과 부 등 관 계 를 정 하여 모순 여 부 를 묻다
해제
var
x:array[-10..200000,1..3]of longint;
y:array[-10..300000,1..3]of longint;
fa,ran:array[0..200000]of longint;
t,n,len,key:longint;
i,j,k,l:longint;
procedure sort(l,r: longint);
var i,j,a,b: longint;
begin
i:=l; j:=r; a:=y[(l+r) div 2,1];
repeat
while y[i,1]<a do inc(i);
while a<y[j,1] do dec(j);
if not(i>j) then
begin
for k:=1 to 3 do
begin b:=y[i,k]; y[i,k]:=y[j,k]; y[j,k]:=b; end;
inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
function get(a:longint):longint;
begin
if fa[a]=a
then exit(a);
fa[a]:=get(fa[a]);
exit(fa[a]);
end;
procedure union(a,b:longint);
begin
if ran[get(a)]>ran[get(b)]
then begin fa[get(b)]:=fa[get(a)]; inc(ran[a]); end
else begin fa[get(a)]:=fa[get(b)]; inc(ran[b]); end;
end;
begin
readln(t);
for l:=1 to t do
begin
readln(n);
for i:=1 to n do
begin
readln(x[i,1],x[i,2],x[i,3]);
y[i*2-1,1]:=x[i,1]; y[i*2-1,2]:=i; y[i*2-1,3]:=1;
y[i*2,1]:=x[i,2]; y[i*2,2]:=i; y[i*2,3]:=2;
end;
sort(1,2*n);
len:=0; y[0,1]:=-1;
for i:=1 to 2*n do
begin
if y[i,1]<>y[i-1,1]
then inc(len);
x[y[i,2],y[i,3]]:=len;
end;
for i:=1 to len do
begin fa[i]:=i; ran[i]:=0; end;
key:=0;
for i:=1 to n do
if (x[i,3]=1)and(x[i,1]<>x[i,2]) then union(x[i,1],x[i,2]);
for i:=1 to n do
if (x[i,3]=0)and(get(x[i,1])=get(x[i,2]))
then begin key:=1; writeln('NO'); break; end;
if key=0
then writeln('YES');
end;
end.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.