Submission #892139

#	Time	Username	Problem	Language	Result	Execution time	Memory
892139		votranngocvy	Valley (BOI19_valley)	C++14	59 / 100	3028 ms	40384 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],timeDFS;
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);
    }
    fini[u] = timeDFS;
}

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]);
}

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));
    }
    vector<int>vec;
    for (int i = 1; i <= s; i++) {
        int x;
        cin >> x;
        vec.push_back(x);
        marked[x] = true;
    }
    dfs(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];
    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 {
            if (marked[x]) cout << 0 << "\n";
            else {
                int ans = inf;
                for (auto y: vec) 
                    if (inSubtree(y,v)) ans = min(ans,f[x] + f[y] - 2 * f[lca(x,y)]);
                if (ans == inf) cout << "oo\n";
                else cout << ans << "\n";
            }
        }
    }
}

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