oj.uz

답안 #16459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16459 2015-08-25T14:17:35 Z hongjun7 두 섬간의 연결 (kriii1_2) C++14
0 / 1
 63 ms 6980 KB 
#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) {
			for (int i = v[c[x + 1]].size(); i--;) {
				int a = v[c[x + 1]][i];
				c[a] = c[x];
				v[c[x]].push_back(a);
			}
			v[c[x + 1]].clear();
		}
		else {
			for (int i = v[c[x]].size(); i--;) {
				int a = v[c[x]][i];
				c[a] = c[x];
				v[c[x + 1]].push_back(a);
			}
			v[c[x]].clear();
		}
		printf("%lld %lld\n", pairans, distans);
	}
}

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 6980 KB Output isn't correct
2 Halted 0 ms 0 KB -