Submission #783038

#	Time	Username	Problem	Language	Result	Execution time	Memory
783038		Charizard2021	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	76 ms	20992 KiB

roadsideadverts

#include<bits/stdc++.h>
using namespace std;
const int N = 500001;
int dp[21][N];
vector<pair<int, int> > adj[N];
int level[N];
int dist[N];
void dfs(int u, int p){
	for(pair<int, int> x : adj[u]){
        int v = x.first;
		if(v != p){
			dp[0][v] = u;
			level[v] = level[u] + 1;
            dist[v] = dist[u] + x.second;
			dfs(v, u);
		}
	}
}
int solve(int x, int k){
	int val = 0;
	while(k > 0){
		if(k % 2 == 1){
			x = dp[val][x];
		}
		val++;
		k >>= 1;
	}
	return x;
}
int solve2(int a, int b){
	if(level[a] > level[b]){
		swap(a, b);
	}
	int difference = level[b] - level[a];
	b = solve(b, difference);
	if(a == b){
		return a;
	}
	for(int i = 20; i >= 0; i--){
		if(dp[i][a] != dp[i][b]){
			a = dp[i][a];
			b = dp[i][b];
		}
	}
	return dp[0][a];
}
int dist2(int a, int b){
    return dist[a] + dist[b] - 2 * dist[solve2(a, b)];
}
int main(){
    int n;
    cin >> n;
	for(int i = 0; i < n - 1; i++){
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
    dist[0] = 0;
	dfs(0, -1);
	for(int i = 1; i < 21; i++){
		for(int j = 0; j < n; j++){
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
    int q;
    cin >> q;
	while(q--){
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        cout << (dist2(a, b) + dist2(b, c) + dist2(c, d) + dist2(d, e) + dist2(e, a))/2 << "\n";
	}
}

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