Submission #8347

#	Time	Username	Problem	Language	Result	Execution time	Memory
8347		ptncks0121	두 섬간의 연결 (kriii1_2)	C++98	1 / 1	56 ms	2260 KiB

2

#include <stdio.h>
  
int N,P[100100];
long long C[100100],CON,DIS;
  
int find(int x)
{
    if (x != P[x]) P[x] = find(P[x]);
    return P[x];
}
  
int main()
{
    int i,x,y;
  
    scanf ("%d",&N);
    for (i=1;i<=N;i++) P[i] = i, C[i] = 1;
    for (i=1;i<N;i++){
        scanf ("%d",&x);
        y = find(x+1); x = find(x);
        if (x == y){fprintf (stderr,"ERR"); return 0;}
        CON += C[x] * C[y];
        DIS -= C[x] * (C[x] - 1) * (C[x] + 1) / 6;
        DIS -= C[y] * (C[y] - 1) * (C[y] + 1) / 6;
        P[y] = x; C[x] += C[y];
        DIS += C[x] * (C[x] - 1) * (C[x] + 1) / 6;
  
        printf ("%lld %lld\n",CON,DIS);
    }
  
    return 0;
}

• Subtask 1: 1 / 1