Submission #19159

#	Time	Username	Problem	Language	Result	Execution time	Memory
19159		Namnamseo	두 섬간의 연결 (kriii1_2)	C++14	1 / 1	37 ms	1864 KiB

2

#include <cstdio>

int par[100010];
int size[100010];

typedef long long ll;

ll c2(int x){ return x*(x+1LL)/2; }

int root(int x){ return (x==par[x])?x:(par[x]=root(par[x])); }

int main()
{
    int n;
    scanf("%d",&n);
    ll X=0, Y=0;
    for(int i=1; i<=n; ++i) par[i]=i, size[i]=1;
    for(int _=1; _<n; ++_){
        int a;
        scanf("%d",&a);
        int L=a, R=root(a+1);
        X += size[L]*1LL*size[R];
        Y += (c2(size[L]-1)*size[R] + c2(size[R]-1)*size[L])+size[L]*1LL*size[R];
        printf("%lld %lld\n",X,Y);
        par[L]=R;
        size[R]+=size[L];
    }
    return 0;
}

• Subtask 1: 1 / 1