Submission #1037151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037151		Macker	Valley (BOI19_valley)	C++17	100 / 100	366 ms	97364 KiB

valley

#include <bits/stdc++.h>

using namespace std;
typedef long double ld;
typedef long long ll;
#define int ll
typedef pair<int, int> pii;

#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define inf LLONG_MAX/2
#define ff first
#define ss second
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define last(s) (*--s.end())
#define first(s) *s.begin()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

signed main()
{
    int n, s, q, e; cin >> n >> s >> q >> e; e--;
    vector<vector<pii>> adj(n);
    vector<pii> edg(n - 1);
    FOR(i, n-1){
        int a, b, c; cin >> a >> b >> c; a--; b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
        edg[i] = {a, b};
    }
    vector<int> sd(n, inf);
    FOR(i, s){
        int a; cin >> a; a--;
        sd[a] = 0;
    }

    vector<vector<pair<int, pii>>> par(n, vector<pair<int, pii>>(30)); // {par, {dist, shopdist}}
    vector<int> dpth(n);
    dpth[e] = 0;
    par[e][0].ff = e;
    function<void(int, int)> dfs = [&](int a, int p){
        for (auto [b, c] : adj[a]) {
            if(b == p) continue;
            dpth[b] = dpth[a] + 1;
            dfs(b, a);
            par[b][0].ff = a;
            par[b][0].ss.ff = c;
            ckmin(sd[a], sd[b] + c);
        }
    };
    dfs(e, e);
    FOR(i, n) par[i][0].ss.ss = min(sd[i], sd[par[i][0].ff] + par[i][0].ss.ff);
    FOR(j, 29) FOR(i, n){
        int p = par[i][j].ff;
        par[i][j + 1].ff = par[p][j].ff;
        par[i][j + 1].ss.ff = par[i][j].ss.ff + par[p][j].ss.ff;
        par[i][j + 1].ss.ss = min(par[i][j].ss.ss, par[p][j].ss.ss + par[i][j].ss.ff);
    }

    while(q--){
        int i, a; cin >> i >> a; a--; i--;
        int low = edg[i].ff;
        if(dpth[edg[i].ss] > dpth[edg[i].ff]) low = edg[i].ss;
        int dpthi = dpth[low];
        int res = sd[a], d = 0;
        for (int j = 29; j >= 0; j--) {
            if(dpth[par[a][j].ff] >= dpthi){
                ckmin(res, par[a][j].ss.ss + d);
                d += par[a][j].ss.ff;
                a = par[a][j].ff;
            }
        }

        if(a != low){
            cout << "escaped" << "\n";
        }
        else{
            if(res == inf) cout << "oo" << endl;
            else cout << res << "\n";
        }
    }
}

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