Submission #5706

#	Time	Username	Problem	Language	Result	Execution time	Memory
5706		baneling100	두 섬간의 연결 (kriii1_2)	C++98	1 / 1	48 ms	2648 KiB

2

#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 / 1