1 solutions

  • 0
    @ 2024-12-10 23:09:37

    C++ :

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    using namespace std;
    #define N 30010
    int f[N],c[N],b[N];
    int n;
    void readln(int &x,int &y){
    	x = y = 0;
    	char ch = getchar();
    	do{
    		ch = getchar();
    		if (isdigit(ch)) x = x * 10 + ch - 48;
    	}while (isdigit(ch));
    	do{
    		ch = getchar();
    		if (isdigit(ch)) y = y * 10 + ch - 48;
    	}while (isdigit(ch));
    	return;
    }
    
    
    int find_Fa(int x){
    	int i = x;
    	while (f[i] != i) i = f[i];
    	int ff = i;
    	i = x;
    	int j;
    	int next;
    	while (i != ff){
    		next = f[i];
    		f[i] = ff;
    		j = next;
    		do{
    			b[i] += b[j];
    			j = f[j];
    		}while (f[j] != j);
    		i = next;
    	}
    	return ff;
    }
    
    void moveship(int x,int y){
    	int fx = find_Fa(x),fy = find_Fa(y);
    	f[f[fx]] = fy;
    	b[fx] = b[fx] + c[fy];
    	c[fy] += c[fx];
    	return;
    }
    
    void check(int x,int y){
    	int fx = find_Fa(x),fy = find_Fa(y);
    	if (fx != fy) puts("-1");
    	else printf("%d\n",abs(b[x] - b[y]) - 1);
    	return;
    }
    
    int main(){
    	for (int i = 1; i < N ; i++) f[i] = i,c[i] = 1,b[i] = 0;
    	scanf("%d",&n);
    	getchar();
    	char ch;
    	int x,y;
    	while (n--){
                    getchar();
    		ch = getchar();
    		readln(x,y);
    		switch (ch){
    			case 'M': moveship(x,y);break;
    			case 'C': check(x,y);break;
    		}
    	}
    	return 0;
    }
    

    Pascal :

    var
     father,before,long:array[0..30005] of longint;
     i,j,t,x,y,sx,sy:longint;
     s:char;
    function get(x:longint):longint;
    var
     f:longint;
    begin
     if father[x]=x then exit(x);
      f:=get(father[x]);
      before[x]:=before[x]+before[father[x]];
      father[x]:=f;
      get:=f;
    end;
    procedure init;
    begin
     readln(t);
     for i:=1 to 30000 do begin father[i]:=i; before[i]:=0; long[i]:=1;end;
    end;
    procedure work;
    begin
     for i:=1 to t do
      begin
       readln(s,x,y);
       if s='M' then
        begin
         sx:=get(x);
         sy:=get(y);
         father[sx]:=sy;
         before[sx]:=long[sy];
         long[sy]:=long[sy]+long[sx];
        end;
      if s='C' then
       begin
        sx:=get(x);
        sy:=get(y);
        if sx<>sy then j:=-1
         else j:=abs(before[x]-before[y])-1;
        writeln(j);
       end;
       end;
     end;
    begin
     init;
     work;
     
    end.
    
    
    • 1

    Information

    ID
    578
    Time
    2000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By