Submission #431941

#	Time	Username	Problem	Language	Result	Execution time	Memory
431941		SirCovidThe19th	Valley (BOI19_valley)	C++14	100 / 100	688 ms	43804 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

const int mx = 1e5+5, ml = 17;

int n, sh, q, e, tin[mx], tout[mx], cnt; 
ll d[mx], dp[mx], up[ml][mx], best[ml][mx]; bool shop[mx];
pii edges[mx]; vector<pii> adj[mx]; 

ll dfs(int node){
    tin[node] = cnt++; ll ret = ((shop[node]) ? d[node] : LLONG_MAX); 
    for (int l = 1; l < ml; l++) up[l][node] = up[l-1][up[l-1][node]];
    for (pii nxt : adj[node])
        if (nxt.f != up[0][node])
            d[nxt.f] = d[node]+nxt.s, up[0][nxt.f] = node, ret = min(ret, dfs(nxt.f));
    dp[node] = ret-d[node]*2; tout[node] = cnt-1; return ret;
}

int main() {
    cin >> n >> sh >> q >> e;
    for (int i = 1; i < n; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
        edges[i] = {a, b};
    }for (int i = 0; i < sh; i++) { int a; cin >> a; shop[a] = 1; }
    dfs(e); memset(best, 0x3f, sizeof(best)); 
    for (int i = 1; i <= n; i++) best[0][i] = dp[up[0][i]]; 
    for (int l = 1; l < ml; l++)
        for (int i = 1; i <= n; i++)
            best[l][i] = min(best[l-1][i], best[l-1][up[l-1][i]]);
    while (q--){
        int i, r; cin >> i >> r; ll ans = dp[r]; int curr = r;
        int root = ((up[0][edges[i].f] == edges[i].s) ? edges[i].f : edges[i].s);
        if (!(tin[root] <= tin[r] and tout[root] >= tout[r])) cout<<"escaped"<<endl;
        else if (dp[root] >= 1e16) cout<<"oo"<<endl; 
        else{
            for (int l = ml-1; l >= 0; l--) 
                if (d[up[l][curr]] >= d[root]) 
                    ans = min(ans, best[l][curr]), curr = up[l][curr];
            cout<<ans+d[r]<<endl;
        }
    }
}

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