Submission #362931

#	Time	Username	Problem	Language	Result	Execution time	Memory
362931		dolphingarlic	Construction of Highway (JOI18_construction)	C++14	100 / 100	646 ms	106604 KiB

construction

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int c[100001], u[100001], v[100001], par[100001];
vector<int> graph[100001];
int heavy[100001], head[100001], depth[100001];
deque<pair<int, int>> hld_vals[100001];

int dfs(int node = 1) {
	int sz = 1, mx = 0;
	for (int i : graph[node]) {
		int csz = dfs(i);
		sz += csz;
		if (csz > mx) mx = csz, heavy[node] = i;
	}
	return sz;
}

void decompose(int node = 1, int h = 1, int d = 1) {
	head[node] = h; depth[node] = d;
	if (heavy[node]) decompose(heavy[node], h, d + 1);
	for (int i : graph[node]) if (i != heavy[node]) decompose(i, i, 1);
}

ll count_inversions(deque<pair<int, int>> &path) {
	map<int, int> comp;
	for (pair<int, int> i : path) comp[i.first];
	int n = 0;
	for (auto &i : comp) i.second = ++n;

	ll ans = 0;
	vector<ll> bit(n + 1);
	for (pair<int, int> i : path) {
		for (int j = comp[i.first] - 1; j; j -= j & -j) ans += bit[j] * i.second;
		for (int j = comp[i.first]; j <= n; j += j & -j) bit[j] += i.second;
	}
	return ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> c[i];
	for (int i = 1; i < n; i++) {
		cin >> u[i] >> v[i];
		graph[u[i]].push_back(v[i]);
		par[v[i]] = u[i];
	}
	dfs(); decompose();

	hld_vals[1].push_back({c[1], 1});
	for (int i = 1; i < n; i++) {
		deque<pair<int, int>> path;
		int curr = v[i];
		while (curr) {
			deque<pair<int, int>> ins;
			int rem = depth[curr] - (curr == v[i]), h = head[curr];
			while (rem) {
				if (hld_vals[h][0].second <= rem) {
					rem -= hld_vals[h][0].second;
					ins.push_front(hld_vals[h][0]);
					hld_vals[h].pop_front();
				} else {
					ins.push_front({hld_vals[h][0].first, rem});
					pair<int, int> upd = {hld_vals[h][0].first, hld_vals[h][0].second - rem};
					hld_vals[h].pop_front();
					hld_vals[h].push_front(upd);
					rem = 0;
				}
			}
			hld_vals[h].push_front({c[v[i]], depth[curr]});
			path.insert(path.end(), ins.begin(), ins.end());
			curr = par[h];
		}
		cout << count_inversions(path) << '\n';
	}
	return 0;
}

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