Submission #497636

#	Time	Username	Problem	Language	Result	Execution time	Memory
497636		zhougz	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	61 ms	10676 KiB

roadsideadverts

/**
 *    author: zhougz
 *    created: 23/12/2021 19:37:06
**/
#include <bits/stdc++.h>

using namespace std;

int n, k, cnt;
const int MAXN = 50'050, MAXK = log2(MAXN) + 1;
vector<pair<int, int>> v[MAXN];
int pre[MAXN], anc[MAXN][MAXK], dist[MAXN], dep[MAXN];

void dfs(int x, int par) {
	pre[x] = cnt++;
	anc[x][0] = par;
	for (int i = 1; i <= k; i++) {
		int half_par = anc[x][i - 1];
		if (half_par == -1) {
			break;
		}
		anc[x][i] = anc[half_par][i - 1];
	}
	for (const auto &[z, w] : v[x]) {
		if (z != par) {
			dist[z] = dist[x] + w;
			dep[z] = dep[x] + 1;
			dfs(z, x);
		}
	}
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) {
		swap(a, b);
	}
	int bal = dep[b] - dep[a];
	for (int i = 0; i <= k; i++) {
		if (bal & (1 << i)) {
			b = anc[b][i];
		}
	}
	assert(dep[a] == dep[b]);
	if (a == b) {
		return a;
	}
	for (int i = k; i >= 0; i--) {
		if (anc[a][i] == anc[b][i]) {
			continue;
		}
		a = anc[a][i];
		b = anc[b][i];
	}
	assert(anc[a][0] == anc[b][0]);
	return anc[a][0];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	k = log2(n);
	for (int i = 0, a, b, w; i < n - 1; i++) {
		cin >> a >> b >> w;
		v[a].emplace_back(b, w);
		v[b].emplace_back(a, w);
	}
	dfs(0, -1);
	int q;
	cin >> q;
	while (q--) {
		int arr[5];
		for (int i = 0; i < 5; i++) {
			cin >> arr[i];
		}
		sort(arr, arr + 5, [&](int a, int b) {
			return pre[a] < pre[b];
		});
		int res = 0;
		for (int i = 0; i < 5; i++) {
			res += dist[arr[i]] + dist[arr[(i + 1) % 5]] - 2 * dist[lca(arr[i], arr[(i + 1) % 5])];
		}
		cout << res / 2 << '\n';
	}
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30