测评机: Xeost[5]
得分: 70分
提交日期: 2010-7-15 9:06:00
有效耗时: 1266毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时156ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时172ms
测试结果6: 通过本测试点|有效耗时203ms
测试结果7: 通过本测试点|有效耗时344ms
测试结果8: 运行错误|栈溢出
测试结果9: 测试结果错误.错误结果为:61594
正确结果应为:1322
测试结果10: 测试结果错误.错误结果为:243
正确结果应为:71
错三个点,我是并查集的初学者!!一个字,菜
var
n,k,i,j,q,p,t:longint;
a,b,c,fa,dist:array[1..50000] of longint;
f:array[1..100000] of boolean;
function getfather(x:longint):longint;
var
g:longint;
begin
if fa[x]=x then exit(x);
g:=getfather(fa[x]);
dist[x]:=(dist[fa[x]]+dist[x]+3) mod 3;
fa[x]:=g;
exit(g);
end;
begin
readln(n,k);
for i:=1 to n do
begin
fa[i]:=i;
dist[i]:=0;
end;
for i:=1 to k do
readln(a[i],b[i],c[i]);
fillchar(f,sizeof(f),true);
for i:=1 to k do
if (b[i]>n) or (c[i]>n) then f[i]:=false;
for i:=1 to k do
if (a[i]=2) and (b[i]=c[i]) then f[i]:=false;
for i:=1 to k do
if f[i] then
begin
p:=getfather(b[i]);
q:=getfather(c[i]);
if p=q then
begin
t:=(dist[c[i]]-dist[b[i]]+3) mod 3;
if t<>a[i]-1 then f[i]:=false;
end
else begin
fa[q]:=p;
dist[q]:=(3+dist[b[i]]+a[i]-1-dist[c[i]]) mod 3;
end;
end;
t:=0;
for i:=1 to k do
if not f[i] then t:=t+1;
writeln(t);
end.
n,k,i,j,q,p,t,a,b,c:longint;
fa,dist:array[0..50000] of longint;
f:longint;
function getfather(x:longint):longint;
var
g:longint;
begin
if fa[x]=0 then exit(x);
if fa[fa[x]]=0 then exit(fa[x]);
g:=getfather(fa[x]);
dist[x]:=(dist[fa[x]]+dist[x]) mod 3;
fa[x]:=g;
exit(g);
end;
begin
readln(n,k);
for i:=1 to n do
begin
fa[i]:=0;
dist[i]:=0;
end;
for i:=1 to k do
begin
readln(a,b,c);
if ((b>n) or (c>n)) or ((a=2) and (b=c)) then f:=f+1
else
begin
p:=getfather(b);
q:=getfather(c);
if p=q then
begin
t:=(dist[c]-dist[b]+3) mod 3;
if t<>a-1 then f:=f+1;
end
else begin
fa[q]:=p;
dist[q]:=(3+dist[b]+a-1-dist[c]) mod 3;
end;
end;
end;
writeln(f);
end.
数组开小了,(ˇˍˇ) 想~