oj.uz

Submission #8348

# Submission time Handle Problem Language Result Execution time Memory
8348 2014-09-13T02:05:26 Z tncks0121 두 섬간의 연결 (kriii1_2) C++
1 / 1
 48 ms 2260 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2260 KB Output is correct
2 Correct 40 ms 2260 KB Output is correct
3 Correct 48 ms 2260 KB Output is correct
4 Correct 40 ms 2260 KB Output is correct
5 Correct 40 ms 2260 KB Output is correct
6 Correct 44 ms 2260 KB Output is correct