Submission #497550

#	Time	Username	Problem	Language	Result	Execution time	Memory
497550		zhougz	Roadside Advertisements (NOI17_roadsideadverts)	C++17	30 / 100	92 ms	13076 KiB

roadsideadverts

/**
 *    author: zhougz
 *    created: 23/12/2021 16:33:58
**/
#include <bits/stdc++.h>

using namespace std;

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

void dfs(int x, int par, int w, int d) {
	anc[x][0] = par;
	dist[x][0] = w;
	dep[x] = d;
	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];
		dist[x][i] = dist[x][i - 1] + dist[half_par][i - 1];
	}
	for (const auto &[z, w] : v[x]) {
		if (z != par) {
			dfs(z, x, w, d + 1);
		}
	}
}

int get_lca(int a, int b) {
	if (dep[a] > dep[b]) {
		swap(a, b);
	}
	int cur_dist = 0;
	int extra = dep[b] - dep[a];
	for (int i = 0; i <= k; i++) {
		if (extra & (1 << i)) {
			cur_dist += dist[b][i];
			b = anc[b][i];
		}
	}
	if (a == b) { // a was already the parent
		return cur_dist;
		//return make_pair(a, cur_dist);
	}
	for (int i = k; i >= 0; i--) {
		if (anc[a][i] == anc[b][i]) {
			continue;
		}
		cur_dist += dist[a][i] + dist[b][i];
		a = anc[a][i];
		b = anc[b][i];
	}
	assert(a != b && anc[a][0] == anc[b][0]);
	return cur_dist + dist[a][0] + dist[b][0];
	//return make_pair(anc[a][0], cur_dist + dist[a][0] + dist[b][0]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(anc, -1, sizeof anc);
	cin >> n;
	k = log2(n - 1);
	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, 0, 0);
	int q;
	cin >> q;
	for (int i = 0, arr[5]; i < q; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> arr[j];
		}
		sort(arr, arr + 5, [&](int a, int b) {
			return dep[a] < dep[b];
		});
		int res = 0;
		for (int j = 1; j < 5; j++) {
			int bst = INT_MAX;
			for (int k = 0; k < j; k++) {
				bst = min(bst, get_lca(arr[k], arr[j]));
			}
			res += bst;
		}
		cout << res << '\n';
	}
	return 0;
}

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