Submission #18565

#	Time	Username	Problem	Language	Result	Execution time	Memory
18565		eaststar	두 섬간의 연결 (kriii1_2)	C++14	1 / 1	55 ms	2644 KiB

2

#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 / 1