Submission #3308

#	Time	Username	Problem	Language	Result	Execution time	Memory
3308		pmpmp	두 섬간의 연결 (kriii1_2)	C++98	0 / 1	48 ms	4992 KiB

2

#include <stdio.h>
int n, a, pa, pb;
long long c, d, cs, ds;
long long h[100000], hh[100000], csum[100000], dsum[100000];
int parent[100000], lenth[100000];

int findp(int pp)
{
    if(parent[pp]!=pp){parent[pp]=findp(parent[pp]);}
    //else{return pp;}
    //else{return parent[pp];}
    return parent[pp];
}

int main ()
{
    
   // freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
    
    int i, j, k;
    scanf("%d", &n);
    for(i=1;i<=n;i++){lenth[i]=1;} for(i=1;i<=n;i++){parent[i]=i;} h[1]=1; hh[2]=1;
    for(i=2;i<=n;i++){h[i]=i+h[i-1];} for(i=3;i<=n;i++){hh[i]=hh[i-1]+h[i-1];}
    for(i=1;i<=n-1;i++)
    {
         scanf("%d", &a);
         pa=findp(a); pb=findp(a+1);
         
         cs=cs-csum[pa]-csum[pb];
         ds=ds-dsum[pa]-dsum[pb];
         
         parent[pb]=pa;
         lenth[pa]=lenth[pa]+lenth[pb]; //printf("%d %d %d %d %d\n", pa, pb, parent[pb], lenth[pa], lenth[pb]);
         c=(lenth[pa]*(lenth[pa]-1))/2;
         d=hh[lenth[pa]-1]+h[lenth[pa]-1];
         
         csum[pa]=c; dsum[pa]=d; //printf("%lld %lld %lld %lld\n", c, d, cs, ds);
         cs=cs+c; ds=ds+d;
         
         printf("%lld %lld\n", cs, ds);
    }
}

• Subtask 1: 0 / 1