oj.uz

Submission #19159

# Submission time Handle Problem Language Result Execution time Memory
19159 2016-02-19T06:05:12 Z Namnamseo 두 섬간의 연결 (kriii1_2) C++14
1 / 1
 37 ms 1864 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1864 KB Output is correct
2 Correct 37 ms 1864 KB Output is correct
3 Correct 0 ms 1864 KB Output is correct
4 Correct 0 ms 1864 KB Output is correct
5 Correct 26 ms 1864 KB Output is correct
6 Correct 0 ms 1864 KB Output is correct