Submission #402588

#	Time	Username	Problem	Language	Result	Execution time	Memory
402588		penguinhacker	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	67 ms	11792 KiB

roadsideadverts

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

#define ll long long
#define ar array

const int mxN=50000;
int n, q, t, pos[mxN], dp[mxN], d[mxN], anc[mxN][16];
vector<ar<int, 2>> adj[mxN];

void dfs(int u=0, int p=-1) {
	pos[u]=t++;
	for (int i=1; i<16; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (ar<int, 2> v : adj[u]) {
		if (v[0]==p)
			continue;
		anc[v[0]][0]=u, d[v[0]]=d[u]+1, dp[v[0]]=dp[u]+v[1];
		dfs(v[0], u);
	}
}

int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=15; ~i; --i)
		if (d[u]<=d[v]-(1<<i))
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=15; ~i; --i)
		if (anc[u][i]^anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<n; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs();
	cin >> q;
	while(q--) {
		int u[5], ans=0;
		for (int i=0; i<5; ++i)
			cin >> u[i], ans+=dp[u[i]];
		sort(u, u+5, [](int a, int b) {return pos[a]<pos[b];});
		int l=u[0];
		for (int i=1; i<5; ++i) {
			int l2=lca(u[i-1], u[i]);
			ans-=dp[l2];
			l=lca(l, l2);
		}
		ans-=dp[l];
		cout << ans << "\n";
	}
	return 0;
}

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