1 solutions
-
0
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