57 条题解

  • 2
    @ 2015-08-02 21:25:44

    const
    maxn=30000;
    type
    node=record
    p,d,l :integer;
    end;
    var
    uf :array[1..maxn]of node;
    n,m :longint;
    a,b,i :longint;
    c :char;
    procedure init;
    var
    i :integer;
    begin
    n:=30000;
    readln(m);
    for i:=1 to n do
    with uf[i] do begin p:=i; l:=1 end;
    end;

    function find(x:integer):integer;
    var
    i,j,p,q :integer;
    begin
    i:=x;
    while uf[i].p<>i do i:=uf[i].p;
    p:=i;
    i:=x;
    while i<>p do
    begin
    q:=uf[i].p;
    uf[i].p:=p;
    j:=q;
    repeat
    inc(uf[i].d,uf[j].d);
    j:=uf[j].p
    until uf[j].p=j;
    i:=q;
    end;
    find:=p;
    end;

    procedure union(a,b:integer);
    var
    t :integer;
    begin
    a:=find(a); b:=find(b);
    uf[a].p:=b;
    uf[a].d:=uf[b].l;
    inc(uf[b].l,uf[a].l)
    end;
    begin
    init;
    for i:=1 to m do
    begin
    readln(c,a,b);
    if c='M' then union(a,b);
    if c='C' then
    if (find(a)=find(b)) then
    writeln(abs(uf[a].d-uf[b].d)-1)
    else writeln(-1)
    end;
    end.

  • 1
    @ 2018-02-15 14:38:11

    #1 Accepted 6ms 772.0 KiB
    #2 Accepted 5ms 2.875 MiB
    #3 Accepted 9ms 892.0 KiB
    #4 Accepted 14ms 996.0 KiB
    #5 Accepted 46ms 1.273 MiB
    #6 Accepted 69ms 1.945 MiB
    #7 Accepted 145ms 4.535 MiB
    #8 Accepted 135ms 6.383 MiB
    #9 Accepted 340ms 6.5 MiB
    #10 Accepted 327ms 6.453 MiB

    很水的做法:
    离线处理最终状态,并查集特判不同列情况

    #include<iostream>
    #include<cmath>
    using namespace std;
    int n=30000,q,fa[30001],f[30001],ta[30001],val[30001];
    struct cz{
        char c;
        int a,b;
    }op[500001];
    int find(int);
    int main(){
        ios::sync_with_stdio(false);
        cin>>q;
        int i,p;
        for(i=1;i<=n;i++){
            fa[i]=f[i]=ta[i]=i;
        }
        for(i=1;i<=q;i++){
            cin>>op[i].c;
            cin>>op[i].a>>op[i].b;
            if(op[i].c=='M'){
                int x=find(op[i].a),y=find(op[i].b);
                fa[x]=y;
                f[x]=ta[y];
                ta[y]=ta[x];
                ta[x]=0;
            }
        }
        p=0;
        for(i=1;i<=n;i++){
            fa[i]=i;
            if(ta[i]==0) continue;
            int v=ta[i];
            val[v]=++p;
            while(f[v]!=v){
                v=f[v];
                val[v]=++p; 
            }
        }
        for(i=1;i<=q;i++){
            int a=find(op[i].a),b=find(op[i].b);
            if(op[i].c=='M'){
                fa[a]=b;
            }else{
                if(a!=b){
                    cout<<-1<<endl;
                    continue;
                }
                cout<<abs(val[op[i].a]-val[op[i].b])-1<<endl;
            }
        }
        return 0;
    }
    int find(int v){
        return fa[v]==v?v:fa[v]=find(fa[v]);
    } 
    
  • 0
    @ 2018-02-05 04:22:27

    从并查集本身树结构思考

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<cmath>
    #define MAXN 30005
    using namespace std;
    
    int ufs[MAXN], dis[MAXN] = {0}, ecnt[MAXN];
    
    void init(int n){
      for(int i=0; i<=n; i++){
        ufs[i] = i;
        ecnt[i] = 1;
      }
      return;
    }
    
    int find(int a){
      int rt = a, ta = a, tta, tcnt;
      int cnt = 0;
      while(ufs[rt] != rt){
        cnt += dis[rt];
        rt = ufs[rt];
      }
      while(ufs[ta] != ta){
        tta = ta;
        tcnt = dis[ta];
        dis[ta] = cnt;
        cnt -= tcnt;
        ta = ufs[ta];
        ufs[tta] = rt;
      }
      return rt;
    }
    
    void unite(int a, int b){
      int rta, rtb;
      int tcnta, tcntb;
      rta = find(a);
      rtb = find(b);
      if(rta == rtb){
        return;
      }
      ufs[rta] = rtb;
      tcnta = ecnt[rta];
      tcntb = ecnt[rtb];
      ecnt[rta] = 0;
      ecnt[rtb] = tcnta + tcntb;
      dis[rta] = tcntb;
      return;
    }
    
    int sameufs(int a, int b){
      if(a == b){
        return 0;
      }
      if(find(a) != find(b)){
        return -1;
      }else{
        return abs(dis[a] - dis[b]) - 1;
      }
    }
    
    int main(){
      int n;
      string s;
      cin >> n;
      int x, y;
      init(30000);
      for(int i=0; i<n; i++){
        cin >> s >> x >> y;
        if(s == "M"){
          unite(x, y);
        }else if(s == "C"){
          cout << sameufs(x, y) << endl;
        }
        
      }
    
      return 0;
    }
    
    
  • 0
    @ 2017-01-16 19:32:42

    wc这道题疯狂拉AC率。
    我写了两份代码,第一份T了最后两个点,然后在第二份中修改,结果每次提交成了第一份。
    TLE的原因是用了cin。被卡常了。真是zz。

  • 0
    @ 2016-10-12 13:04:45

    #include<iostream>
    using namespace std;
    int pre[30001];
    int find(int x)
    {
    int r=x;
    while(pre[r]!=r)
    r=pre[r];

    int i=x,j;
    while(i!=j)
    {
    j=pre[r];
    pre[i]=r;
    i=j;
    }
    return r;
    }
    void mix(int x,int y)
    {
    int fx=find(x),fy=find(y);
    if(fx!=fy)
    pre[fx]=fy;
    }
    int main()
    {
    int i,t,a,b,j;
    char g;
    for(i=1;i<=30000;i++)
    pre[i]=i;
    cin>>t;
    for(i=1;i<=t;i++)
    {
    cin>>g>>a>>b;
    if(g=='M')
    {
    mix(a,b);
    }
    if(g=='C')
    {
    if(find(a)==find(b))
    cout<<"1"<<endl;
    else
    cout<<"-1"<<endl;
    }
    }

    }

  • 0
    @ 2016-08-24 08:36:23
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int INF = 1000000000;
    const int maxn = 30000 + 10;
    
    int p[maxn], d[maxn], cnt[maxn];
    
    int find (int x) { 
        if (x == p[x]) return x;
        int root = find(p[x]);
        d[x] += d[p[x]];
        return p[x] = root;
    }
    
    void comb (int x, int y) {
        int a = find(x), b = find(y);
        p[b] = a;
        d[b] = cnt[a];
        cnt[a] += cnt[b];
    }
    
    int query (int x, int y) {
        int a = find(x), b = find(y);
        if (a != b) return -1;
        return abs(d[x]-d[y])-1;
    }
    
    int main () 
    {
        freopen("in.txt", "r", stdin);
        for (int i = 0; i < maxn; i++) { p[i] = i; cnt[i] = 1;}
        int T; scanf("%d\n", &T);
        while (T--) {
            char code;
            int i, j;
            scanf("%c %d %d\n", &code, &i, &j);
            if (code == 'M') comb(j, i);
            else printf("%d\n", query(i, j));
        }
        return 0;
    }
    
  • 0
    @ 2016-07-22 11:30:32

    #include<cstdio>

    #include<cmath>

    const int Max=30001;

    int t,father[Max],x,y,r[Max],root[Max];

    char ch;

    int find(int k){

    if(k==father[k]) return k;

    int temp=find(father[k]);

    r[k]=r[father[k]]+r[k];

    father[k]=temp;

    return temp;

    }

    int main(){

    scanf("%d",&t);

    for(int i=1;i<Max;i++){

    father[i]=i; r[i]=0,root[i]=1; //r表示到根节点的距离

    } //root 表示该树节点个数

    while(t--){

    getchar();

    scanf("%c%d%d",&ch,&x,&y);

    int tempx=find(x),tempy=find(y);

    if(ch=='M'){

    father[tempx]=tempy; //X 接到 y

    r[tempx]=root[tempy]; //更新距离

    root[tempy]+=root[tempx]; //更新树节点个数

    }

    else if(tempx!=tempy) printf("-1\n");

    else printf("%d\n",(int)fabs(r[x]-r[y])-1);

    }

    return 0;

    }

  • 0
    @ 2016-07-09 16:50:39
    #include <iostream> 
    #include <cstdio> 
    #include <cmath> 
    #include <algorithm>
    using namespace std;
    int f[30001],s[30001],sum[30001];
    char ch_buffer;
    int signum;
    inline void read(int&x){
        x=0;char c;
        for(c=getchar();c<'0'||c>'9';c=getchar());     
        for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0';
    }
    int find(int v){
        if(f[v]!=v){
               int p=find(f[v]);
               s[v]+=s[f[v]];
               f[v]=p;
        }
        return f[v];
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(NULL);
       //freopen("in.in","r",stdin);
        int f1,f2,num,a,b; 
        char ch;
        read(num);
        for(int i=1;i<=30000;i++){sum[i]=1;f[i]=i;}
        for(int i=1;i<=num;i++){
            ch=getchar();
            read(a),read(b);
            f1=find(a),f2=find(b);
            //cout<<a<<b;
            if(ch=='M'){
            f[f1]=f2;
            s[f1]=sum[f2];
            sum[f2]+=sum[f1];
            }
            else{
            if(f1==f2)cout<<abs(s[a]-s[b])-1<<"\n";
            else cout<<"-1\n";
        }
    }
    return 0;
    }
    
  • 0
    @ 2016-02-25 19:47:31
    //直接并查集~~
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #define MAXN 31000
    using namespace std;
    
    struct node
    {
        int fa;
        int d;//i飞船前面有多少飞船 b
        int l;//当i是并查集根时,i后面有多少飞船 c
    };
    char flag;
    node f[MAXN];
    int i,t,x,y;
    
    int getfather (int x)
    {
        int t;
        if (x==f[x].fa) return x;
        t=f[x].fa;
        f[x].fa=getfather(f[x].fa);
        f[x].d+=f[t].d;
        return f[x].fa;
    }
    
    void merg (int x,int y)
    {
        int tx=getfather(x);
        int ty=getfather(y);
        if (tx!=ty)
        {
            f[tx].fa=ty;
            f[tx].d=f[ty].l+1;
            f[ty].l=f[ty].l+f[tx].l+1;
        }
    }
    
    int query (int x,int y)
    {
        if (getfather(x)==getfather(y))
            return (abs(f[x].d-f[y].d)-1);
        else return -1;
    }
    
    int main()
    {
        for (i=1;i<=MAXN;i++)
        {
            f[i].fa=i;
            f[i].d=0;
            f[i].l=0;
        }
        scanf("%d\n",&t);
        for (i=1;i<=t;i++)
        {
            scanf("%c %d %d\n",&flag,&x,&y);
            if (flag=='M')
                merg(x,y);
            else
                printf("%d\n",query(x,y));
        }
        return 0;
    }
    
  • 0
    @ 2015-11-15 22:56:23

    P1443银河英雄传说
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1443 银河英雄传说
    递交时间 2015-11-15 22:55:41
    代码语言 C++
    评测机 VijosEx
    消耗时间 5238 ms
    消耗内存 628 KiB
    评测时间 2015-11-15 22:55:49

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 628 KiB, score = 10

    测试数据 #3: Accepted, time = 62 ms, mem = 624 KiB, score = 10

    测试数据 #4: Accepted, time = 202 ms, mem = 628 KiB, score = 10

    测试数据 #5: Accepted, time = 483 ms, mem = 624 KiB, score = 10

    测试数据 #6: Accepted, time = 499 ms, mem = 628 KiB, score = 10

    测试数据 #7: Accepted, time = 639 ms, mem = 624 KiB, score = 10

    测试数据 #8: Accepted, time = 1856 ms, mem = 628 KiB, score = 10

    测试数据 #9: Accepted, time = 1482 ms, mem = 624 KiB, score = 10

    Accepted, time = 5238 ms, mem = 628 KiB, score = 100

    why so slow

    代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>

    using namespace std;

    int pre[30000 + 2] , size[30000 + 2] , tail[30000 + 2];
    int n , a , b , x , y;
    char s[10];

    int find( int x )
    {
    if( pre[x] == x ) return x;
    int pos = pre[x];
    pre[x] = find( pre[x] );
    size[x] += size[pos];
    return pre[x];
    }

    inline void merge( int a , int b )
    {
    pre[ find( a ) ] = find( b );
    }

    inline int Abs( int x )
    {
    return x > 0 ? x : -x;
    }

    int main()
    {
    scanf( "%d" , &n );
    for( register int i = 1 ; i <= 30000 ; i++ )
    pre[i] = i , tail[i] = 1;
    while( n-- )
    {
    scanf( "%s %d %d" , s , &a , &b );
    if( s[0] == 'C' )
    {
    if( find( a ) != find( b ) ) puts( "-1" );
    else printf( "%d\n" , Abs( size[a] - size[b] ) - 1 );
    }
    else
    {
    x = find( a ) , y = find( b );
    merge( a , b );
    size[ x ] += tail[ y ];
    tail[ y ] += tail[ x ];
    }
    }
    return 0;
    }

  • 0
    @ 2015-03-14 14:22:22

    感觉只能用链式并查集来维护一些神奇的东西?.....
    使用启发式合并达到O(nlogn)的复杂度......

  • 0
    @ 2014-10-03 14:55:27

    #include<cmath>
    #include<cstdio>
    #include<iostream>
    using namespace std;
    char t;
    int m,q,a,b,f[30001],o[30001]={0},c[30001];
    void r(int&d)
    {
    char t=getchar();
    while(t<'0'||t>'9')
    t=getchar();
    for(d=0;t>='0'&&t<='9';t=getchar())
    d=(d<<3)+(d<<1)+t-'0';
    }
    int find(int n)
    {
    int d;
    if(n==f[n])
    return n;
    else
    {
    d=find(f[n]);
    o[n]+=o[f[n]];
    f[n]=d;
    return f[n];
    }
    }
    bool e(int x,int y)
    {
    int p,q;
    p=find(x);
    q=find(y);
    if(p==q)
    return 1;
    else
    {
    f[q]=p;
    o[q]+=c[p];
    c[p]+=c[q];
    return 0;
    }
    }
    main()
    {
    char k[100];
    int d,i,j;
    cin>>q;
    for(i=1;i<30001;i++)
    {
    f[i]=i;
    c[i]=1;
    }
    for(i=0;i!=q;i++)
    {
    t=getchar();
    while(t!='M'&&t!='C')
    t=getchar();
    r(a);
    r(b);
    if(t=='M')
    e(a,b);
    else
    if(find(a)==find(b))
    {
    d=abs(o[b]-o[a])-1;
    j=1;
    if(d<0)
    {
    cout<<'-';
    d=-d;
    }
    if(!d)
    cout<<0;
    for(;d;d/=10,j++)
    k[j]=d%10+'0';
    for(j--;j;j--)
    cout<<k[j];
    cout<<endl;
    }
    else
    cout<<-1<<endl;
    }
    }

  • 0
    @ 2014-08-24 13:50:49

    #include<cstdio>

    int n=30000,m,q;
    int ai,bi;
    int fath[30001];
    int count[30001];
    int before[30001];
    char t;
    inline void _out(int x,int j=1)

    {

    char t[100];

    if(x<0)

    {

    putchar('-');

    x=-x;

    }

    if(x==0) printf("0");

    for(;x;x/=10,j++) t[j]=x%10+'0';

    for(j--;j;j--) putchar(t[j]);

    putchar('\n');

    }

    inline void _read(int& data)
    {
    char t=getchar();
    while(t<'0'||t>'9') t=getchar();
    for(data=0;t>='0'&&t<='9';t=getchar()) data=(((data)<<3)+((data)<<1))+t-'0';
    }

    int getfather(int num)
    {
    int dad;
    if(num==fath[num]) return num;
    else
    {
    dad=getfather(fath[num]);
    before[num]=before[num]+before[fath[num]];
    fath[num]=dad;
    return fath[num];
    }
    }
    bool merge(int x,int y)
    {
    int fx,fy ;
    fx=getfather(x);
    fy=getfather(y);
    if (fx==fy) return true;
    else
    {
    fath[fy]=fx;
    before[fy]=before[fy]+count[fx];
    count[fx]=count[fx]+count[fy];
    return false;
    }
    }

    inline void _init()
    {
    scanf("%d",&q);
    for(int i=1;i<=n;++i)
    {fath[i]=i;count[i]=1;before[i]=0;}
    }
    inline int abs(int a)
    {return a<0?(-a):a;}
    int main()
    {
    _init();
    for(int i=0;i!=q;++i)
    {
    t=getchar();
    while(t!='M'&&t!='C') t=getchar();
    if(t=='M'){_read(ai);_read(bi); merge(ai,bi);}
    else
    { _read(ai);_read(bi);
    if(getfather(ai)==getfather(bi))_out((abs(before[bi]-before[ai]))-1);
    else {putchar('-');putchar('1');putchar('\n');}
    }
    }
    return 0;
    }

  • 0
    @ 2013-10-14 15:57:54

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    long f[30100],s[30100],sum[30100];
    int getfather(int v){
    if (f[v]!=v){
    int p=getfather(f[v]);
    s[v]+=s[f[v]];
    f[v]=p;
    }return f[v];
    }
    int main(){
    int f1,f2,num,a,b; char ch;
    scanf("%d\n",&num);
    for(int i=1;i<=30000;i++) {s[i]=0; sum[i]=1; f[i]=i;}
    for(int i=1;i<=num;i++){
    scanf("%c %d %d\n",&ch,&a,&b);
    f1=getfather(a),f2=getfather(b);
    if(ch=='M'){
    f[f1]=f2;
    s[f1]=sum[f2];
    sum[f2]+=sum[f1];
    }else if(ch=='C'){
    if(f1==f2) printf("%d\n",abs(s[a]-s[b])-1);

    else printf("-1\n");

    }
    }
    return 0;
    }

  • 0
    @ 2013-08-13 12:55:31

    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:57:26: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1]' [-Wformat]
    测试数据 #0: Accepted, time = 7 ms, mem = 1004 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1004 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1004 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 1000 KiB, score = 10
    测试数据 #4: Accepted, time = 62 ms, mem = 1004 KiB, score = 10
    测试数据 #5: Accepted, time = 93 ms, mem = 1004 KiB, score = 10
    测试数据 #6: Accepted, time = 140 ms, mem = 1000 KiB, score = 10
    测试数据 #7: Accepted, time = 203 ms, mem = 1004 KiB, score = 10
    测试数据 #8: Accepted, time = 343 ms, mem = 1004 KiB, score = 10
    测试数据 #9: Accepted, time = 468 ms, mem = 1000 KiB, score = 10
    Accepted, time = 1331 ms, mem = 1004 KiB, score = 100
    #include <cstdio>
    #include <cstring>

    using namespace std;

    #define MAXN 30001

    int father[MAXN];
    int tail[MAXN],head[MAXN];
    int suff[MAXN];

    int t;
    char c[1];

    int ABS(int x){
    if (x<0){
    return -x;
    }
    return x;
    }

    int INSERT(int x,int y){
    father[x]=y;
    suff[x]++;
    return 0;
    }

    int find(int x){
    int i=x;
    int k=0;
    while (father[i]){
    k+=suff[i];
    k--;
    i=father[i];
    }
    k++;
    int j=x;
    while (father[j]){
    int h=father[j],z=suff[j];
    suff[j]=k;
    k-=(z-1);
    father[j]=i;
    j=h;
    }
    return i;
    }

    int main(){
    memset(father,0,sizeof(father));
    for (int i=0;i++<MAXN;){
    tail[i]=head[i]=i;
    suff[i]=1;
    }
    scanf("%d",&t);
    while (t--){
    int x,y;
    scanf("%s%d%d",&c,&x,&y);
    if (c[0]=='M'){
    int k=tail[find(x)];
    INSERT(find(x),tail[find(y)]);
    tail[find(y)]=k;
    } else {
    if (find(x)!=find(y)){
    printf("-1\n");
    } else printf("%d\n",ABS(suff[x]-suff[y])-1);
    }
    }
    return 0;
    }

  • 0
    @ 2010-04-16 12:36:13

    VJ脑残的输出

    无语了

  • 0
    @ 2010-03-18 13:48:00

    我无语...自己机上测这条题(使用VJ数据)近乎秒,这里超时+格式错误+答案错误....T-T

  • 0
    @ 2009-11-19 20:26:26

    #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

  • 0
    @ 2009-11-11 18:44:14

    编译通过...

    ├ 测试数据 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分,浪费了巨多的时间,结果竟然是系统的输出问题。。。。囧

信息

ID
1443
难度
7
分类
数据结构 | 并查集 点击显示
标签
递交数
3339
已通过
677
通过率
20%
被复制
1
上传者