社区讨论
哪位大神帮看一下?最后一点RE……
P1955[NOI2015] 程序自动分析参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi5hsrpl
- 此快照首次捕获于
- 2025/11/19 12:18 4 个月前
- 此快照最后确认于
- 2025/11/19 12:18 4 个月前
明天NOIP……不想再耗这题了……哪位有空帮我看一下谢谢~最后一个点RE,怀疑内存泄漏,结果释放后居然只有10分……好吧,希望哪位有空的帮看看……
做法就是把不相等的攒起来,相等用并查集,最后逐个判断不相等是否成立
以下代码(未释放内存)
CPPtype lianbiao=^point;
point=record
data,code:longint;
next:lianbiao;
end;
var a,b,c,d,e,x,y,gb,t,n,top:longint;
hash:array[1..1000000] of lianbiao;
equal:array[1..100000] of longint;
unequal:array[1..100000,1..2] of longint;
flag:boolean;
function cal(x:longint):longint;
begin
x:=(x-1) mod 100000+1;
exit(x);
end;
function reha(x:longint):longint;
var v:lianbiao;
o:longint;
begin
o:=cal(x);
v:=hash[o];
while (v^.data<>x) do v:=v^.next;
exit(v^.code);
end;
function find(v:longint):longint;
begin
if equal[v]<>v then equal[v]:=find(equal[v]);
find:=equal[v];
end;
procedure union(x,y:longint);
begin
x:=find(x);
y:=find(y);
equal[x]:=y;
end;
procedure lisan(p:longint);
var o:lianbiao;
v:longint;
begin
v:=cal(p);
if hash[v]=nil then begin
new(hash[v]);
hash[v]^.data:=p; hash[v]^.code:=gb; hash[v]^.next:=nil; inc(gb);
exit;
end;
o:=hash[v];
while (o<>nil) and (o^.data<>p) do
o:=o^.next;
if o^.data=p then exit;
new(o);
o^.data:=p; o^.code:=gb; o^.next:=nil; inc(gb);
end;
begin
readln(t);
for a:=1 to t do
begin
readln(n); gb:=1; flag:=true; top:=1;
for b:=1 to 100000 do equal[b]:=b;
for b:=1 to 100000 do hash[b]:=nil;
for b:=1 to n do
begin
readln(x,y,e);
lisan(x); lisan(y);
if e=1 then union(equal[reha(x)],equal[reha(y)])
else if e=0 then
begin
unequal[top,1]:=x; unequal[top,2]:=y;
inc(top);
end;
end;
dec(top);
while top>=1 do
begin
if find(reha(unequal[top,1]))=find(reha(unequal[top,2])) then
begin flag:=false; break; end;
dec(top);
end;
if flag then writeln('YES') else writeln('NO');
end;
end.
回复
共 4 条回复,欢迎继续交流。
正在加载回复...