Submission #850875

#	Time	Username	Problem	Language	Result	Execution time	Memory
850875		annabeth9680	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	48 ms	12384 KiB

roadsideadverts

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 5e4+11;
vector<pair<int,int>> adj[MAXN];
int tin[MAXN], tout[MAXN], par[MAXN][20], dep[MAXN], dist[MAXN];
int timer;
void dfs(int u, int p){
    tin[u] = ++timer;
    for(auto c : adj[u]){
        if(c.f != p){
            dep[c.f] = dep[u]+1; par[c.f][0] = u; dist[c.f] = dist[u]+c.s;
            for(int i = 1;i<20;++i) par[c.f][i] = par[par[c.f][i-1]][i-1];
            dfs(c.f,u);
        }
    }
    tout[u] = timer;
}
int calcanc(int u, int k){
    for(int i = 19;i>=0;--i){
        if(k >= (1<<i)){
            u = par[u][i];
            k -= (1<<i);
        }
    }
    return u;
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u,v);
    u = calcanc(u,dep[u]-dep[v]);
    for(int i = 19;i>=0;--i){
        if(par[u][i] != par[v][i]){
            u = par[u][i]; v = par[v][i];
        }
    }
    return (u == v) ? u : par[u][0];
}
bool checkanc(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
bool cmp(int x, int y){
    return tin[x] < tin[y];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; cin >> N;
    for(int i = 0;i<N-1;++i){
        int u,v,w; cin >> u >> v >> w;
        adj[u].push_back({v,w}); adj[v].push_back({u,w});
    }
    dfs(0,-1);
    int Q; cin >> Q;
    while(Q--){
        vector<int> q(5);
        for(int i = 0;i<5;++i) cin >> q[i];
        sort(q.begin(),q.end(),cmp);
        vector<int> path; path.push_back(q[0]);
        int ans = 0;
        for(int i = 0;i<5;++i){
            while(path.size() >= 2 && checkanc(lca(path.back(),q[i]), path[path.size()-2])){
                ans += dist[path.back()]-dist[path[path.size()-2]];
                //cout << path.back() << " " << path[path.size()-2] << " " << dist[path.back()]-dist[path[path.size()-2]] << "\n";
                path.pop_back();
            }
            if(checkanc(path.back(),q[i])){
                path.push_back(q[i]);
            }
            else{
                int a = lca(path.back(),q[i]);
                ans += dist[path.back()]-dist[a];
                path.pop_back();
                path.push_back(a);
                path.push_back(q[i]);
            }
        }
        while(path.size() >= 2){
            ans += dist[path.back()]-dist[path[path.size()-2]];
            path.pop_back();
        }
        cout << ans << "\n";
    }
    return 0;
}

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