社区讨论

哪位大神帮看一下?最后一点RE……

P1955[NOI2015] 程序自动分析参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi5hsrpl
此快照首次捕获于
2025/11/19 12:18
4 个月前
此快照最后确认于
2025/11/19 12:18
4 个月前
查看原帖
明天NOIP……不想再耗这题了……哪位有空帮我看一下谢谢~最后一个点RE,怀疑内存泄漏,结果释放后居然只有10分……好吧,希望哪位有空的帮看看……
做法就是把不相等的攒起来,相等用并查集,最后逐个判断不相等是否成立
以下代码(未释放内存)
CPP
type 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 条回复,欢迎继续交流。

正在加载回复...