#include

#include

using namespace std;

struct a

{

int d;

int p;

int z;

}f[30001];

int find(int i)

{

if(f[i].p!=i)

{

int r=find(f[i].p);

f[i].d+=f[f[i].p].d;

f[i].p=r;

}

return f[i].p;

}

int main(void)

{

//FILE *fp1=fopen("galaxy.in","r"),*fp2=fopen("galaxy.out","w");

int t,i,a,b,ar,br;

char p;

for(i=1;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 384ms

├ 测试数据 10：答案正确... 259ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：715ms

今天真是见识到了vj的输出之脑瘫，害我WA了N次的40分，浪费了巨多的时间，结果竟然是系统的输出问题。。。。囧

orz

write(ans);

inc(count);

if count mod 10000=0 then writeln;

这是什么原理……

做这个要把队列战舰数和当前战舰之前的数目调整好，需要足够的耐心和细心，调了好长时间，然后输出超时.......幸好来膜拜了下题解不然真就撞墙去了，再次bs vijos 的输出。对并查集的启发式还是不太了解，哪位牛讲下吧.....郁闷啊....

还有楼下，你打的是传说中的标程吧...还打错了，怎么会秒杀的？汗颜......

输出究竟啥意思？写了是不超时了，那位大牛解释下原因？

我写的就是并查集……

不该输出40分，改了秒杀……

var

father,count,before:array[1..30000]of longint;

i,j,k,n,t,num:longint;

s:char;

function getfather(x:longint):longint;

var i:longint;

begin

if father[x]=0 then exit(x)

else

begin

i:=getfather(father[x]);

before[x]:=before[x]+before[father[x]];

father[x]:=i;

exit(father[x]);

end;

end;

procedure try(s:char;j,k:longint);

var i,x,y:longint;

begin

if s='M' then

begin

x:=getfather(j);

y:=getfather(k);

if xy then

begin

father[x]:=y;

before[x]:=before[x]+count[y];

count[y]:=count[y]+count[x];

end;

end;

if s='C' then

begin

x:=getfather(j);

y:=getfather(k);

if xy then begin write('-1');

inc(num);

if num mod 10000=0 then writeln;

end

else begin

write(abs(before[j]-before[k])-1);

inc(num);

if num mod 10000=0 then writeln;

end;

end;

end;

begin

readln(t);

for i:=1 to 30000 do

count[i]:=1;

fillchar(father,sizeof(father),0);

fillchar(before,sizeof(before),0);

for i:=1 to t do

begin

readln(s,j,k);

try(s,j,k);

end;

end.

擦，vj的输出真脑瘫……

只把有解时候的输出改成了write，忘改无解的了，结果TLE N次，我很无奈……我的通过率……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：27ms

我很奇怪时间怎么这么短。。。。

难道Evolution SmdCn比Puppy还强？

我提交这道题各把VE和ES卡了20s，还以为出什么严重的问题了呢。。。（我可不想被封号）

program vijos_1443;

const

maxN=30000;

type

TNode=record

fa,before,count:longint

end;

var

n:longint;

d:array[1..maxN] of TNode;

procedure init;

var

i:longint;

begin

for i:=1 to maxN do

with d[i] do begin

fa:=i;

count:=1;

before:=0;

end;

end;

function root(i:longint):longint;

begin

if d[i].fa=i then

root:=i

else begin

root:=root(d[i].fa);

inc(d[i].before,d[d[i].fa].before);

d[i].fa:=root;

end;

end;

procedure union(x,y:longint);

var

i,j:longint;

begin

i:=root(x);

j:=root(y);

d[i].fa:=j;

inc(d[i].before,d[j].count);

inc(d[j].count,d[i].count);

end;

procedure ask(x,y:longint);

begin

if root(x)root(y) then write(-1)

else write(abs(d[x].before-d[y].before)-1);

end;

procedure main;

var

i,x,y:longint;

c:char;

begin

readln(n);

for i:=1 to n do begin

read(c); readln(x,y);

case c of

'M':union(x,y);

'C':begin

ask(x,y);

if i mod 10000=0 then writeln

else write(' ');

end;

end;

end;

end;

begin

init;

main;

end.

....输出特无语。。。。

---|---|---|---|--转自 陈亮宇神牛---|---|---|---|---|---|---|---|-

writeln 太慢

所以

write(ans);

inc(count);

if count mod 10000=0 then writeln;

（做p1081的经验）

切记切记 否则40...

Accepted 有效得分：100 有效耗时：56ms

什么时候有这题的？？一直不知道，但是不是特难，就是并查集的变种…………

只不过输出………………好像是VJ的老问题吧。

额...

这个输出未免太诡异了吧...

mod 10000=0

的方法是如何发现的？

评测机还能测出不同的结果？

真WS。。

数开小了。。

还有这个脑残的输出

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 244ms

├ 测试数据 10：答案正确... 244ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：538ms

ORZ LSSSSSSSS的亮牛

感谢 VJ PUPPY的支持

无语的题目.....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 369ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：644ms

puppy不是很稳定啊……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 306ms

├ 测试数据 10：答案正确... 197ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：584ms

第一次写并查集。。超时两次。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 197ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：366ms

30 行AC

精华一句话

f[x]:=f[x]+f[fa[x]];

输出真萎缩……

并查集的变种