제출 #3301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3301		pmpmp	두 섬간의 연결 (kriii1_2)	C++98	0 / 1	44 ms	4016 KiB

2

#include <iostream>
#include <algorithm>
#include <stdio.h>
int n, a, pa, pb;
long long c, d;
long long h[100000], hh[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);
         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];
         printf("%lld %lld\n", c, d);
    }
}

• Subtask 1: 0 / 1