Submission #783048

#	Time	Username	Problem	Language	Result	Execution time	Memory
783048		Charizard2021	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	66 ms	12900 KiB

roadsideadverts

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