| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 3358 | 2013-08-30T16:54:23 Z | cuk123 | 두 섬간의 연결 (kriii1_2) | C++ | 0 ms | 0 KB |
#include<stdio.h>
int n, parent[100001], size[100001];
long long r1, r2;
int find(int idx){
if(parent[idx]==idx)
return idx;
return parent[idx]=find(parent[idx]);
}
void Union(int a, int b){
int tmp;
long long n1, n2;
a=find(a);
b=find(b);
if(size[a]<size[b]){
tmp=a;
a=b;
b=tmp;
}
n1=(long long)size[a];
n2=(long long)size[b];
parent[b]=a;
r1+=n1*n2;
r2+=(n1*n2(n2+1)/2LL+n2*n1(n1-1)/2LL);
size[a]+=size[b];
}
int main(){
int i, num;
scanf("%d", &n);
for(i=1;i<n+1;++i){
parent[i]=i;
size[i]=1;
}
r1=r2=0;
for(i=1;i<n;++i){
scanf("%d", &num);
Union(num, num+1);
printf("%lld %lld\n", r1, r2);
}
}