Submission #1036823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036823		trucmai	Valley (BOI19_valley)	C++17	100 / 100	182 ms	75188 KiB

valley

#include <bits/stdc++.h>
#ifdef LOCAL
    #include "/home/trcmai/code/tools.h"
    #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
    #define debug(x...)
#endif
using namespace std;
#define all(a) a.begin(), a.end()
#define ll long long
#define endl '\n'
const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
const ll INF = 1e18;
int n,s,q,root;
vector<pair<int,ll>>g[N];
bool shop[N];
ll dep[N],mn[N],dp[N][LOG]; 
int h[N],tin[N],tout[N],up[N][LOG];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    auto solver=[&](){
        cin>>n>>s>>q>>root;
        vector<tuple<int,int,ll>>edge(n + 1);
        for(int i = 1;i < n;++i){
            int u,v; ll w; 
            cin>>u>>v>>w; 
            g[u].emplace_back(v,w);
            g[v].emplace_back(u,w);
            edge[i] = {u,v,w};
        }
        fill(mn + 1,mn + n + 1,INF);
        for(int i = 1;i <= s;++i){
            int ver; cin>>ver; 
            mn[ver] = 0;
        }
        auto dfs1=[&](auto &&self,int u,int p)->void{
            for(auto &[v,w] : g[u]){
                if(v == p) continue;
                self(self,v,u);
                mn[u] = min(mn[u],mn[v] + w);
            }
        };
        int timer = 0;
        auto dfs2=[&](auto &&self,int u,int p)->void{
            tin[u] = ++timer;
            for(auto &[v,w] : g[u]){
                if(v == p) continue;
                dep[v] = dep[u] + w; 
                h[v] = h[u] + 1;
                up[v][0] = u;
                dp[v][0] = mn[u] - dep[u];
                for(int i = 1;i < LOG;++i){
                    up[v][i] = up[up[v][i-1]][i-1];
                    dp[v][i] = min(dp[v][i-1],dp[up[v][i-1]][i-1]);
                }
                self(self,v,u);
            }
            tout[u] = timer;
        };
        auto lift=[&](int u,int anc){
            int k = h[u] - h[anc];
            ll res = mn[u] - dep[u];
            for(int i = 0;i < LOG;++i){
                if(k>>i&1){
                    res = min(res,dp[u][i]);
                    u = up[u][i];
                }
            }
            return res;
        };
        dfs1(dfs1,root,0);
        dfs2(dfs2,root,0);
        while(q--){
            int idx,vert; cin>>idx>>vert;
            auto [u,v,w] = edge[idx];
            if(v == up[u][0]) swap(u,v);
            if(!(tin[v] <= tin[vert] && tout[v] >= tout[vert])){
                cout<<"escaped"<<endl;
                continue;
            }
            ll dist = lift(vert,v) + dep[vert];
            if(dist >= 1e14) cout<<"oo"<<endl;
            else cout<<dist<<endl;
        }
    };
    int t = 1; // cin>>t;
    while (t--) solver();
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41