Submission #16465

#	Time	Username	Problem	Language	Result	Execution time	Memory
16465		gs14004	두 섬간의 연결 (kriii1_2)	C++14	1 / 1	60 ms	1868 KiB

2

#include <cstdio>
typedef long long lint;

struct disj{
	int pa[100005], sz[100005];
	void init(int n){
		for(int i=0; i<=n; i++){
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	int getsize(int x){
		return sz[find(x)];
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		pa[q] = p;
		sz[p] += sz[q];
	}
}disj;

lint f(int x){
	return 1ll * x * (x-1) / 2;
}

int main(){
	int n;
	scanf("%d",&n);
	disj.init(n);
	lint p1 = 0, p2 = 0;
	for(int i=0; i<n-1; i++){
		int x;
		scanf("%d",&x);
		p1 -= f(disj.getsize(x));
		p1 -= f(disj.getsize(x+1));
		p1 += f(disj.getsize(x) + disj.getsize(x+1));
		p2 += f(disj.getsize(x)) * disj.getsize(x+1);
		p2 += f(disj.getsize(x+1)) * disj.getsize(x);
		p2 += 1ll * disj.getsize(x) * disj.getsize(x+1);
		disj.uni(x, x+1);
		printf("%lld %lld\n",p1, p2);
	}
}

• Subtask 1: 1 / 1