Submission #587467

#	Time	Username	Problem	Language	Result	Execution time	Memory
587467		NekoRolly	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	51 ms	10556 KiB

roadsideadverts

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+4;
const int inf = 1e9;

int n,q,n1;
int up[N][16],dis[N],L[N],R[N];
vector<pair<int,int>> adj[N];

void dfs(int u,int p){ up[u][0] = p, L[u] = n1++;
	for (int i=1; i<16; i++) up[u][i] = up[up[u][i-1]][i-1];
	for (auto [v, w] : adj[u]) if (v != p){
		dis[v] = dis[u] + w; dfs(v, u);
	}
	R[u] = n1;
}

bool isa(int a,int b){
	return L[a] <= L[b] && R[b] <= R[a];
}

int lca(int a,int b){
	if (isa(a, b)) return a;
	if (isa(b, a)) return b;
	for (int i=15; i>=0; i--) if (!isa(up[a][i], b))
		a = up[a][i];
	return up[a][0];
}

int Dis(int a,int b){
	return dis[a] + dis[b] - 2*dis[lca(a, b)];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;

	for (int i=1,a,b,w; i<n; i++){ cin >> a >> b >> w;
		adj[a].push_back({b, w}), adj[b].push_back({a, w});
	}

	dfs(0, 0); cin >> q;

	for (int a[5],ans,aux; q; q--){
		for (int i=0; i<5; i++) cin >> a[i];
		ans = Dis(a[0], a[1]);
		for (int i=2; i<5; i++){ aux = inf;
			for (int j=0; j<i; j++) for (int k=j+1; k<i; k++)
				aux = min(aux, Dis(a[i], a[j]) + Dis(a[i], a[k]) - Dis(a[j], a[k]));
			ans += aux/2;
		}
		cout << ans << "\n";
	}

    return 0;
}

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