讨论 / 大家来讨论一下[七夕星夜]吧(用并查集TLE了的某人)
grsiy 2011-10-29 14:45:00
点我顶贴 收藏 删除
我是用带删除(用虚拟节点)的并查集做这道题,

但目前只能过前4个点,后面第五个点TLE了,

之后就全输出2(估计是超时导致),直到最后一个点又TLE了。

我把我的FP代码贴下吧,希望大家能帮我看看哪儿还能优化。

(或者帮我把代码转成C/CPP试一下?)

const

MAXN=200010; MAXM=1000010; MAXT=400010;

TURN_OFF=0; TURN_ON=1;

SMALLER=-1; EQUAL=0; BIGGER=1;

type

t_type=record v,s,t:longint; end;

var

n,m:longint;

t_size:longint;

t:array[1..MAXT] of t_type;

st:array[1..MAXN] of longint; ln:longint;

aim,link:array[1..MAXM] of longint;

ufs_size:longint;

pos:array[1..MAXN] of longint;

light:array[1..MAXN] of boolean;

fat,rank:array[1..MAXT] of longint;

i,j,u,v,limit:longint;

ans:longint;

procedure in_edge(u,v:longint);

begin

inc(ln);

aim[ln]:=v;

link[ln]:=st[u];

st[u]:=ln;

end;

function cmp(i,j:t_type):longint;

begin

if i.t<j.t then exit(SMALLER);

if i.t>j.t then exit(BIGGER);

if i.s<j.s then exit(SMALLER);

if i.s>j.s then exit(BIGGER);

exit(EQUAL);

end;

procedure qsort(l,r:longint);

var

i,j:longint;

mid,tmp:t_type;

begin

if l>=r then exit;

mid:=t[l+random(r-l+1)];

i:=l; j:=r;

repeat

while cmp(t[i],mid)=SMALLER do inc(i);

while cmp(t[j],mid)=BIGGER do dec(j);

if not(i>j) then

begin

tmp:=t[i]; t[i]:=t[j]; t[j]:=tmp;

inc(i); dec(j);

end;

until i>j;

qsort(l,j); qsort(i,r);

end;

function get_fat(u:longint):longint;

begin

if fat[u]<>u then

fat[u]:=get_fat(fat[u]);

exit(fat[u]);

end;

procedure crt_new(i:longint);

begin

inc(ufs_size);

pos[i]:=ufs_size;

fat[pos[i]]:=pos[i];

rank[pos[i]]:=1;

end;

procedure union_to(u,v:longint);

begin

u:=get_fat(u); v:=get_fat(v);

fat[u]:=v;

inc(rank[v],rank[u]);

rank[u]:=0;

end;

begin

read(n,m);

t_size:=0;

for i:=1 to n do

begin

read(limit);

for j:=1 to limit do

begin

read(u);

inc(t_size);

t[t_size].v:=i;

t[t_size].s:=TURN_ON;

t[t_size].t:=u;

read(v);

inc(t_size);

t[t_size].v:=i;

t[t_size].s:=TURN_OFF;

t[t_size].t:=v+1

end;

end;

randomize; qsort(1,t_size);

fillchar(st,sizeof(st),0); ln:=0;

for i:=1 to m do

begin

read(u,v);

in_edge(u,v);

in_edge(v,u);

end;

ufs_size:=0; ans:=1;

fillchar(light,sizeof(light),false);

for i:=1 to t_size do

begin

if t[i].s=TURN_ON then

begin

u:=t[i].v;

if not light[u] then

begin

light[u]:=true;

crt_new(u);

j:=st[u];

while j<>0 do

begin

v:=aim[j];

if light[v] then

begin

union_to(pos[v],pos[u]);

if rank[pos[u]]>ans then

ans:=rank[pos[u]];

end;

j:=link[j];

end;

end;

end

else

begin

u:=t[i].v;

if light[u] then

begin

light[u]:=false;

dec(rank[get_fat(pos[u])]);

end;

end;

end;

writeln(ans);

end.

#1 grsiy@2011-08-13 01:18:00
回复 删除
大家来交流下各自的做法吧~
#2 grsiy@2011-08-13 01:32:00
回复 删除
补充一下,并查集的删点方法我是在这儿看到的:

http://hi.baidu.com/newmyl/blog/item/f39d8019786c6b7ddbb4bd2d.html

#3 594250@2011-08-14 18:23:00
回复 删除
请教一下为什么第四个点会错

测试结果1: 通过本测试点|有效耗时484ms

测试结果2: 通过本测试点|有效耗时360ms

测试结果3: 通过本测试点|有效耗时218ms

测试结果4: 测试结果错误.错误结果为:3

正确结果应为:2

测试结果5: 选手程序运行超过时限

测试结果6: 测试结果错误.错误结果为:3

正确结果应为:18

测试结果7: 测试结果错误.错误结果为:3

正确结果应为:14

测试结果8: 测试结果错误.错误结果为:3

正确结果应为:14

测试结果9: 选手程序运行超过时限

测试结果10: 测试结果错误.错误结果为:3

正确结果应为:1

提交代码: view sourceprint?01.var

02.

god:array[1..200000,0..100] of integer;

03.

fa:array[1..200000] of longint;

04.

s:array[1..100000,1..3] of integer;

05.

i,j,m,n,t,p,q,all,ans,a,b:longint;

06.function sf(i:longint):longint;

07.begin

08.

if fa[i]=i then sf:=i

09.

else begin sf:=sf(fa[i]); fa[i]:=sf; end;

10.end;

11.begin

12.

readln(n,m);

13.

for i:=1 to n do fa[i]:=i;

14.

for i:=1 to n do

15.

begin

16.

read(t);

17.

for j:=1 to t do

18.

begin

19.

inc(all);

20.

read(p,q);

21.

s[all,1]:=i; s[all,2]:=p; s[all,3]:=q;

22.

end;

23.

end;

24.

for i:=1 to m do

25.

begin

26.

readln(a,b);

27.

fa[a]:=sf(a);

28.

fa[b]:=sf(b);

29.

if fa[a]<>fa[b] then fa[fa[a]]:=fa[b];

30.

end;

31.

for i:=1 to n do fa[i]:=sf(i);

32.

ans:=1;

33.

fillchar(god,sizeof(god),0);

34.

for i:=1 to all do

35.

for j:=s[i,2] to s[i,3] do

36.

begin

37.

inc(god[fa[s[i,1]],j]);

38.

if god[fa[s[i,1]],j]>ans then ans:=god[fa[s[i,1]],j];

39.

end;

40.

writeln(ans);

41.end.

#4 lijiaming12340@2011-10-29 14:45:00
回复 删除
估计是超时了。。。
查看更多回复
提交回复