Submission #1097756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097756		votranngocvy	Valley (BOI19_valley)	C++14	100 / 100	146 ms	62292 KiB

valley

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

#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 5;
const int inf = 1e18;
int dp[N],f[N],marked[N],par[N][25],mini[N][25],h[N],tin[N],tout[N],timeDFS;
vector<pii>g[N];
pii edge[N];

void dfs(int u,int p) {
    dp[u] = inf;
    for (auto x: g[u]) {
        int v = x.fi,w = x.se;
        if (v == p) continue;
        f[v] = f[u] + w;
        dfs(v,u);
        dp[u] = min(dp[u],dp[v] + w);
    }
    if (marked[u]) dp[u] = 0;
}

void dfs2(int u,int p) {
    tin[u] = ++timeDFS;
    par[u][0] = p;
    for (auto x: g[u]) {
        int v = x.fi;
        if (v == p) continue;
        mini[v][0] = dp[u] - f[u];
        h[v] = h[u] + 1;
        dfs2(v,u);
    }
    tout[u] = timeDFS;
}

int get(int u,int v) {
    int len = h[u] - h[v],ans = inf;
    for (int i = 18; i >= 0; i--)
        if (len >> i & 1) {
            ans = min(ans,mini[u][i]);
            u = par[u][i];
        }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,s,q,e;
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        edge[i] = {u,v};
    }
    for (int i = 1; i <= s; i++) {
        int x;
        cin >> x;
        marked[x] = 1;
    }
    for (int i = 0; i <= 18; i++)
        for (int u = 1; u <= n; u++) mini[u][i] = inf;
    dfs(e,e);
    dfs2(e,e);
    for (int i = 1; i <= 18; i++)
        for (int u = 1; u <= n; u++) {
            par[u][i] = par[par[u][i - 1]][i - 1];
            mini[u][i] = min(mini[u][i - 1],mini[par[u][i - 1]][i - 1]);
        }
    while (q--) {
        int i,r;
        cin >> i >> r;
        int u = edge[i].fi,v = edge[i].se;
        if (h[u] > h[v]) swap(u,v);
        if (tin[v] <= tin[r] && tin[r] <= tout[v]) {
            int ans = min(dp[r],f[r] + get(r,v));
            if (ans == inf) cout << "oo\n";
            else cout << ans << "\n";
        }
        else cout << "escaped\n";
    }
}

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