oj.uz

Submission #16460

# Submission time Handle Problem Language Result Execution time Memory
16460 2015-08-25T14:21:56 Z hongjun7 두 섬간의 연결 (kriii1_2) C++14
1 / 1
 79 ms 13236 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) {
			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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 11356 KB Output is correct
2 Correct 70 ms 11248 KB Output is correct
3 Correct 75 ms 11044 KB Output is correct
4 Correct 51 ms 11196 KB Output is correct
5 Correct 61 ms 13236 KB Output is correct
6 Correct 39 ms 7844 KB Output is correct