Submission #587474

#	Time	Username	Problem	Language	Result	Execution time	Memory
587474		gg123_pe	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	113 ms	9980 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std; 
 
typedef long long ll; 
#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 50005; 
const ll inf = 2e18; 


int n, a[6], d[N], tin[N], tout[N], c, p[N][16]; 
vector <pair<int,int>> adj[N]; 
vector <int> aux; 

void dfs(int u, int f){
    p[u][0] = f; 
    f(i,1,16) p[u][i] = p[p[u][i-1]][i-1];

    tin[u] = c++; 

    for(auto p: adj[u]){
        int v = p.first, w = p.second; 
        if(v == f) continue; 
        d[v] = d[u] + w; 
        dfs(v, u); 
    }
    tout[u] = c++;
}

bool is(int u, int v){
    return tin[u] <= tin[v] and tout[u] >= tout[v]; 
}

int lca(int u, int v){
    if(is(u, v)) return u; 
    if(is(v, u)) return v; 


    fa(i,15,0){
        if(p[u][i] == 0 or is(p[u][i], v)) continue; 
        u = p[u][i];
    }
    return p[u][0];
}
int main(){
    cin >> n; 

    f(i,1,n){
        int u, v, w; 
        cin >> u >> v >> w; 

        u++, v++; 
        adj[u].push_back({v, w}); 
        adj[v].push_back({u, w}); 
    }

    dfs(1, 0); 

    int qe; cin >> qe; 


    while(qe--){
        bool fe = 0; 
        vector <pair<int,int>> v; 
        set <int> s; 

        f(i,1,6){
            cin >> a[i]; 
            a[i]++;
            if(a[i] == 1) fe = 1; 
            v.push_back({tin[a[i]], a[i]});
            s.insert(a[i]);
        }

        if(!fe){
            v.push_back({tin[1], 1}); 
            s.insert(1);
        }

        sort(v.begin(), v.end()); 

        int ans = 0, l = v.size(); 

        f(i,1,l){
            //cout << v[i].second << " " << v[i-1].second << " " << lca(v[i].second, v[i-1].second) << "\n";
            s.insert(lca(v[i].second, v[i-1].second));
        }

        v.clear(); 
        for(int x: s) v.push_back({tin[x], x}); 

        sort(v.begin(), v.end()); 

        stack <int> q; 
        q.push(1);

        l = v.size();

        f(i,1,l){
            int vi = v[i].second; 
            while(1){
                int x = q.top();
                if(is(x, vi)){
                    //cout << x << " " << vi << " " << d[vi] - d[x] << "\n";
                    ans += d[vi] - d[x];
                    if(x == 1){
                        aux.push_back(vi);
                    }
                    q.push(vi);
                    break; 
                }
                q.pop();
            }
        }
        
        if(aux.size() == 1 and !fe){
            ans -= d[aux[0]];  
        }
        aux.clear();
        cout << ans << "\n"; 
    }
    return 0; 
}

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