但目前只能过前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.
http://hi.baidu.com/newmyl/blog/item/f39d8019786c6b7ddbb4bd2d.html
测试结果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.