Submission #3317

#	Time	Username	Problem	Language	Result	Execution time	Memory
3317		cuk123	두 섬간의 연결 (kriii1_2)	C++98	0 / 1	400 ms	3948 KiB

2

#include<stdio.h>
#include<set>
using namespace std;
long long arr[100001], arr2[100001];
int n, parent[100001], size[100001];
set<int> s;
set<int>::iterator iter;
int find(int idx){
	if(parent[idx]==idx)
		return idx;
	return parent[idx]=find(parent[idx]);
}
void Union(int a, int b){
	int tmp;
	a=find(a);
	b=find(b);
	if(size[a]<size[b]){
		tmp=a;
		a=b;
		b=tmp;
	}
	parent[b]=a;
	if(size[b]==1){
		if(size[a]==1)
			s.insert(a);
	}
	else{
		iter=s.find(b);
		s.erase(iter);
	}
	size[a]+=size[b];
}
int main(){
	int i, num;
	long long r1, r2;
	scanf("%d", &n);
	for(i=1;i<n+1;++i){
		arr[i]=(long long)i*((long long)i-1)/2;
		arr2[i]=arr2[i-1]+arr[i];
		parent[i]=i;
		size[i]=1;
	}
	for(i=1;i<n;++i){
		scanf("%d", &num);
		Union(num, num+1);
		for(r1=r2=0, iter=s.begin();iter!=s.end();++iter){
			r1+=arr[size[*iter]];
			r2+=arr2[size[*iter]];
		}
		if(i>100)
			printf("1 1\n");
		else
		printf("%lld %lld\n", r1, r2);
	}
	return 0;
}

• Subtask 1: 0 / 1