oj.uz

답안 #5706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5706 2014-05-14T08:23:20 Z baneling100 두 섬간의 연결 (kriii1_2) C++
1 / 1
 48 ms 2648 KB 
#include <stdio.h>

long long N, anc[100001], Size[100001], Ans1, Ans2;

void input(void)
{
    int i;

    scanf("%lld",&N);
    for(i=1 ; i<=N ; i++)
    {
        anc[i]=i;
        Size[i]=1;
    }
}

long long find_anc(long long temp)
{
    long long x=temp, temp2;

    while(anc[x]!=x)
    {
        x=anc[x];
    }
    while(anc[temp]!=x)
    {
        temp2=anc[temp];
        anc[temp]=x;
        temp=temp2;
    }
    return x;
}

void process(void)
{
    int i;
    long long temp, x;

    for(i=1 ; i<=N-1 ; i++)
    {
        scanf("%lld",&temp);
        x=find_anc(temp);
        anc[temp+1]=x;
        Ans1+=Size[x]*Size[temp+1];
        Ans2+=Size[x]*Size[temp+1]*(Size[temp+1]+1)/2+Size[temp+1]*(Size[x]-1)*Size[x]/2;
        Size[x]+=Size[temp+1];
        Size[temp+1]=0;
        printf("%lld %lld\n",Ans1,Ans2);
    }
}

int main(void)
{
    input();
    process();

    return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 2648 KB Output is correct
2 Correct 48 ms 2648 KB Output is correct
3 Correct 40 ms 2648 KB Output is correct
4 Correct 40 ms 2648 KB Output is correct
5 Correct 32 ms 2648 KB Output is correct
6 Correct 36 ms 2648 KB Output is correct