Submission #1082353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082353		vuavisao	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	41 ms	9752 KiB

roadsideadverts

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 50'000 + 10;


int n, q;
vector<pair<int, int>> g[N];

int Lg, dist[N], parent[20][N];
int cnt, in[N];
int sDist[N];

void dfs(int u, int p) {
	in[u] = ++ cnt;
	for (const auto& x : g[u]) {
		int v = x.first, w = x.second;
		if (v == p) continue;
		parent[0][v] = u;
		dist[v] = dist[u] + 1;
		sDist[v] = sDist[u] + w;
		dfs(v, u);
	}
};

int lca(int u, int v) {
	if (dist[u] < dist[v]) swap(u, v);

	int delta = dist[u] - dist[v];
	for (int lg = Lg; lg >= 0; -- lg) {
		if (((delta >> lg) & 1)) {
			u = parent[lg][u];
		}
	}
	if (u == v) return u;
	
	for (int lg = Lg; lg >= 0; -- lg) {
		if (parent[lg][u] != parent[lg][v]) {
			u = parent[lg][u];
			v = parent[lg][v];
		}
	}
	return parent[0][u];
}

int getSdist(int u, int p) {
	return sDist[u] - sDist[p];
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n;
	for (int i = 2; i <= n; ++ i) {
		int u, v, w; cin >> u >> v >> w;
		++ u, ++ v;
		g[u].push_back(make_pair(v, w));
		g[v].push_back(make_pair(u, w));
	}
	
	Lg = __lg(n);
	dist[1] = 1; dfs(1, 0);
	for (int lg = 1; lg <= Lg; ++ lg) {
		for (int u = 1; u <= n; ++ u) {
			parent[lg][u] = parent[lg - 1][parent[lg - 1][u]];
		}
	}

	cin >> q;
	while (q -- > 0) {
		int ver[5];
		for (int i = 0; i < 5; ++ i) cin >> ver[i], ++ ver[i];
		sort(ver, ver + 5, [&] (int u, int v) -> bool {
			return in[u] < in[v];
		});
		int anc = lca(ver[0], ver[1]);
		for (int i = 2; i < 5; ++ i) {
			anc = lca(anc, ver[i]);
		}
		int res = getSdist(ver[0], anc);
		for (int i = 1; i < 5; ++ i) {
			res += getSdist(ver[i], lca(ver[i], ver[i - 1]));
		}
		cout << res << '\n';
	}
	return (0 ^ 0);
}

/// Code by vuavisao

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