제출 #16460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16460		hongjun7	두 섬간의 연결 (kriii1_2)	C++14	1 / 1	79 ms	13236 KiB

2

#include <stdio.h>
#include <vector>
using namespace std;
#define MN 100005
typedef long long ll;
int n, x, c[MN];
vector <int> v[MN];
ll pairans, distans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) c[i] = i, v[i].push_back(i);
	for (int k = 1; k < n; k++) {
		scanf("%d", &x);
		ll X = (ll)(v[c[x]].size());
		ll Y = (ll)(v[c[x + 1]].size());
		pairans += X * Y;
		distans += Y*(Y + 1) / 2LL * X + (X - 1)*X / 2LL * Y;
		if (X > Y) {
			int C = c[x + 1];
			for (int i = v[C].size(); i--;) {
				int a = v[C][i];
				c[a] = c[x];
				v[c[x]].push_back(a);
			}
			v[C].clear();
		}
		else {
			int C = c[x];
			for (int i = v[C].size(); i--;) {
				int a = v[C][i];
				c[a] = c[x + 1];
				v[c[x + 1]].push_back(a);
			}
			v[C].clear();
		}
		printf("%lld %lld\n", pairans, distans);
	}
}

• Subtask 1: 1 / 1