Submission #731817

#	Time	Username	Problem	Language	Result	Execution time	Memory
731817		Trunkty	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	253 ms	32964 KiB

roadsideadverts

#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,q;
vector<vector<int>> roads[50005];
int jump[50005][21],dist[50005][21],dep[50005];
int curr=0;

void dfs(int x, int p){
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            jump[i[0]][0] = x;
            dist[i[0]][0] = i[1];
            dep[i[0]] = dep[x]+1;
            dfs(i[0],x);
        }
    }
}

int lca(int a, int b){
    curr = 0;
    if(dep[a]>dep[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dep[b]-(1<<j)>=dep[a]){
            curr += dist[b][j];
            b = jump[b][j];
        }
    }
    if(a==b){
        return a;
    }
    for(int j=20;j>=0;j--){
        if(jump[a][j]!=jump[b][j]){
            curr += dist[a][j];
            curr += dist[b][j];
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    curr += dist[a][0]+dist[b][0];
    return jump[a][0];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        roads[a].push_back({b,c});
        roads[b].push_back({a,c});
    }
    dfs(0,-1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            jump[i][j] = jump[jump[i][j-1]][j-1];
            dist[i][j] = dist[i][j-1]+dist[jump[i][j-1]][j-1];
        }
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int a,b,c,d,e,ans=0;
        cin >> a >> b >> c >> d >> e;
        set<int> s = {a,b,c,d,e};
        while(s.size()>1){
            vector<vector<int>> v;
            for(int j:s){
                for(int k:s){
                    if(j==k){
                        continue;
                    }
                    int p = lca(j,k);
                    v.push_back({dep[p],curr,p,j,k});
                }
            }
            sort(v.begin(),v.end(),greater<vector<int>>());
            s.erase(v[0][3]);
            s.erase(v[0][4]);
            ans += v[0][1];
            s.insert(v[0][2]);
        }
        cout << ans << "\n";
    }
	return 0;
}

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