oj.uz

Submission #18565

# Submission time Handle Problem Language Result Execution time Memory
18565 2016-02-09T08:46:58 Z eaststar 두 섬간의 연결 (kriii1_2) C++14
1 / 1
 55 ms 2644 KB 
#include <stdio.h>
int g[100010],rnk[100010];
long long cnt[100010],pcnt,sum;
int seek(int n){return g[n]==n?n:g[n]=seek(g[n]);}
long long f(long long x){return (x-1)*x*(x+1)/6;}
void union_find(int a,int b){
    a=seek(a),b=seek(b);
    if(a==b)return;
    pcnt+=cnt[a]*cnt[b];
    sum+=f(cnt[a]+cnt[b])-f(cnt[a])-f(cnt[b]);
    if(rnk[a]<rnk[b])g[a]=b,cnt[b]+=cnt[a];
    else{
        if(rnk[a]==rnk[b])++rnk[a];
        g[b]=a,cnt[a]+=cnt[b];
    }
}
int main(){
    int i,n,k;
    scanf("%d",&n);
    for(i=1;i<=n;++i)g[i]=i,cnt[i]=1;
    for(i=1;i<n;++i){
        scanf("%d",&k);
        union_find(k,k+1);
        printf("%lld %lld\n",pcnt,sum);
    }
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2644 KB Output is correct
2 Correct 55 ms 2644 KB Output is correct
3 Correct 0 ms 2644 KB Output is correct
4 Correct 50 ms 2644 KB Output is correct
5 Correct 40 ms 2644 KB Output is correct
6 Correct 54 ms 2644 KB Output is correct