Submission #1223627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223627		chaeryeong	Construction of Highway (JOI18_construction)	C++20	0 / 100	13 ms	328 KiB

construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
int n, c[MAXN];
array <int, 2> ee[MAXN];
int p[MAXN], dep[MAXN], v[MAXN];
void solve () {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y;
		ee[i] = {x, y};
		p[y] = x;
		dep[y] = 1 + dep[x];
	}
	v[1] = c[1];
	int CNT = 0;
	for (int i = 1; i < n; i++) {
		int x = ee[i][0], y = ee[i][1];
		vector <int> d;
		while (true) {
			d.push_back(v[x]);
			if (x == 1) {
				break;
			}
			x = p[x];
		}
		reverse(d.begin(), d.end());
		set <int> ee;
		for (auto j : d) {
			ee.insert(j);
		}
		CNT += ee.size();
		int ans = 0;
		for (int j = 0; j < (int)d.size(); j++) {
			for (int k = j + 1; k < (int)d.size(); k++) {
				ans += d[j] > d[k];
			}
		}
		cout << ans << '\n';
		int t = c[y];
		while (true) {
			v[y] = t;
			if (y == 1) {
				break;
			}
			y = p[y];
		}
	}
	assert(CNT <= 4 * n);
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84