Submission #892286

#	Time	Username	Problem	Language	Result	Execution time	Memory
892286		votranngocvy	Valley (BOI19_valley)	C++14	23 / 100	144 ms	61116 KiB

valley

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

#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int par[N][25],h[N],f[N],fini[N],start[N],Min[N][25],timeDFS,dp[N];
vector<pii>g[N],edge;
bool marked[N];

void dfs(int u,int p) {
    par[u][0] = p;
    start[u] = ++timeDFS;
    for (auto x: g[u]) {
        int v = x.fi,w = x.se;
        if (v == p) continue;
        f[v] = f[u] + w;
        h[v] = h[u] + 1;
        dfs(v,u);
        dp[u] = min(dp[u],dp[v] + w);
    }
    fini[u] = timeDFS;
}

void dfs1(int u,int p) {
    Min[u][0] = dp[u] - f[u];
    for (auto x: g[u]) {
        int v = x.fi;
        if (v == p) continue;
        dfs1(v,u);
    }
}

int lca(int u,int v) {
    if (h[u] < h[v]) swap(u,v);
    for (int i = 19; i >= 0; i--)
        if (h[par[u][i]] >= h[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; i--)
        if (par[u][i] != par[v][i]) u = par[u][i],v = par[v][i];
    return par[u][0];
}

bool inSubtree(int v,int u) {
    return (start[u] <= start[v] && fini[v] <= fini[u]);
}

int get(int u,int v) {
    int len = h[u] - h[v],ans = inf;
    for (int i = 19; i >= 0; i--)
        if (len & (1 << i)) {
            u = par[u][i];
            ans = min(ans,Min[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,c;
        cin >> u >> v >> c;
        g[u].push_back(mp(v,c));
        g[v].push_back(mp(u,c));
        edge.push_back(mp(u,v));
    }
    for (int i = 1; i <= n; i++) dp[i] = inf;
    for (int i = 1; i <= s; i++) {
        int x;
        cin >> x;
        dp[x] = 0;
    }
    dfs(e,e);
    dfs1(e,e);
    for (int i = 1; i <= 19; i++)
        for (int u = 1; u <= n; u++) {
            par[u][i] = par[par[u][i - 1]][i - 1];
            Min[u][i] = min(Min[u][i - 1],Min[par[u][i - 1]][i - 1]);
        }
    while (q--) {
        int idx,x;
        cin >> idx >> x;
        int u = edge[idx - 1].fi,v = edge[idx - 1].se;
        if (v == par[u][0]) swap(u,v);
        if (!inSubtree(x,v)) cout << "escaped\n";
        else {
            int ans = min(dp[x],f[x] + get(x,v));
            if (ans == inf) cout << "oo\n";
            else cout << ans << "\n";
        }
    }
}

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