Submission #783058

#	Time	Username	Problem	Language	Result	Execution time	Memory
783058		Charizard2021	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	1072 ms	15724 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 timeIn[N];
long long timeOut[N];
long long dist[N];
long long timeVal = 0;
void dfs(long long u, long long p){
    timeIn[u] = timeVal;
    timeVal++;
	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);
		}
	}
    timeOut[u] = timeVal;
    timeVal++;
}
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--){
        vector<pair<long long, long long> > v;
        for(int i = 0; i < n; i++){
            long long x;
            cin >> x;
            v.push_back(make_pair(timeIn[x], x));
        }
        sort(v.begin(), v.end());
        long long ans = 0;
        for(int i = 0; i < 5; i++){
            ans += dist2(v[i].second, v[(i + 1) % 5].second);
        }
        cout << ans/2 << "\n";
	}
}

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