洛谷P1196 [NOI2002] 银河英雄传说

　　题目传送门

　　首先分析题目，数据范围特别大，500000组询问直接模拟肯定会超时，这里其实很容易可以想到用并查集。我们定义三个数组：fa[]表示每一个飞船的队首，front[]表示每一搜飞船到队首的距离，num[]表示以该飞船为队首的队伍中飞船的数量。每次M操作时就将x的队首的num值清空，并将fa值改变为y的队首，再将front值更新即可。询问时只要判断fa是否相等就可以了，不相等的话直接输出-1,否则输出abs(front[x]-front[y])-1。

　　Code：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<iomanip>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=3e4+;

int n,fa[N],dis[N],cnt[N];

inline int read()

{

  char ch=getchar();int num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

  while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

  return flag?-num:num;

}

inline int Abs(int x)

{return x>?x:-x;}

inline int find(int x)

{

  if(fa[x]==x)return x;

  int fx=find(fa[x]);

  dis[x]+=dis[fa[x]];

  return fa[x]=fx;

}

int main()

{

  n=read();

  char s;int x,y;

  for(int i=;i<=;i++)

    fa[i]=i,dis[i]=,cnt[i]=;

  for(int i=;i<=n;i++){

    cin>>s;

    x=read();y=read();

    int fx=find(x),fy=find(y);

    if(s=='M'){

      if(fx==fy)continue;

      dis[fx]+=cnt[fy];

      fa[fx]=fy;

      cnt[fy]+=cnt[fx];

      cnt[fx]=;}

    else{

      if(fx!=fy)printf("-1\n");

      else printf("%d\n",Abs(dis[x]-dis[y])-);

    }

  }

  return ;

}

巴特西

洛谷P1196 [NOI2002] 银河英雄传说

最新文章

热门文章