Submission #1223632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223632		chaeryeong	Construction of Highway (JOI18_construction)	C++20	16 / 100	2094 ms	3024 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];
	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());
		vector <pair <int, int>> gg;
		for (int j = 0; j < (int)d.size(); j++) {
			int l = j;
			while (l + 1 < (int)d.size() && d[l + 1] == d[j]) {
				l++;
			}
			gg.push_back({d[j], l - j + 1});
			j = l;
		}
		int ans = 0;
		for (int j = 0; j < (int)gg.size(); j++) {
			for (int k = j + 1; k < (int)gg.size(); k++) {
				ans += (gg[j].first > gg[k].first) * (gg[j].second * gg[k].second);
			}
		}
		cout << ans << '\n';
		int t = c[y];
		while (true) {
			v[y] = t;
			if (y == 1) {
				break;
			}
			y = p[y];
		}
	}
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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