【CodeVS 1540】銀河英雄伝説2002年NOI全国コンクール
1317 ワード
noiこんな水?久しぶりに自分でA題を見ないで~~~~~~~~権を持って調べて集めます!CodeVSのデータが規定に合わない??めちゃくちゃな文字がありますか?私が注釈した読み込みを見て!またテストしたばかりの洛谷は注釈された一言でCadeVSデータが規定に合わないことをAで説明することもできます!
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define INF 100000000
#define MAXN 1000000 // 10^6
int fa[MAXN],depth[MAXN],m;
int F(int x)
{
int tmp=fa[x];
if(fa[x]!=x)
{
fa[x]=F(fa[x]);
depth[x]+=depth[tmp];
}
return fa[x];
}
int wa[MAXN];
int W(int x)
{
if(wa[x]!=x) wa[x]=W(wa[x]);
return wa[x];
}
int main()
{
scanf("%d",&m);char c;
for(int i=1;i<=30000;i++) fa[i]=i,wa[i]=i;
for(int x,y,i=1;i<=m;i++)
{
// getchar(),c=getchar();
cin>>c;
scanf("%d %d",&x,&y);
if(c=='M')
{
if(F(x)!=F(y))
{
int s=F(x),t=W(y);
fa[s]=t;
wa[t]=s;
depth[s]=1;
}
}
if(c=='C')
{
if(F(x)!=F(y))
printf("-1
");
else
F(x),F(y),printf("%d
",abs(depth[x]-depth[y])-1);
}
}
return 0;
}