Submission #841313

#	Time	Username	Problem	Language	Result	Execution time	Memory
841313		ArashJafariyan	Valley (BOI19_valley)	C++17	100 / 100	180 ms	39004 KiB

valley

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

#define pb push_back

const int lg = 17 + 2, maxn = 1e5 + 4;
const ll inf = 1ll << 62, maxa = 1e15;

int n, s, q, e, low[maxn], anc[maxn][lg], cnt[maxn];
ll mn[maxn], d[maxn], cost[maxn][lg];
bitset<maxn> mark;
vector<array<int, 3>> g[maxn];

void dfs(int v, int par) {
    if (v != e) {
        anc[v][0] = par;
        for (int i = 1; i < lg; ++i) {
            int u = anc[v][i - 1];
            if (u != -1) {
                anc[v][i] = anc[u][i - 1];
            }
        }
    }

    if (mark[v]) {
        mn[v] = d[v];
    }

    for (auto [u, w, ind] : g[v]) {
        if (u != par) {
            cnt[u] = cnt[v] + 1;
            d[u] = d[v] + w;
            low[ind] = u;

            dfs(u, v);
    
            mn[v] = min(mn[v], mn[u]); 
        }
    } 
}

void calc(int v, int par) {
    cost[v][0] = mn[v] - (d[v] << 1);
    for (int i = 1; i < lg; ++i) {
        ll t = cost[v][i - 1];
        int u = anc[v][i - 1];
        if (u != -1) {
            t = min(t, cost[u][i - 1]);
        }
        cost[v][i] = t;
    }

    for (auto [u, w, ind] : g[v]) {
        if (u != par) {
            calc(u, v);
        }
    }
}

int up(int v, ll dis) {
    for (int i = 0; i < lg; ++i) {
        if (((1 << i) & dis) && v != -1) {
            v = anc[v][i];
        }
    }
    return v;
}

ll ans(int v, ll dis) {
    ll ret = inf;
    for (int i = 0; i < lg; ++i) {
        if (((1 << i) & dis) && v != -1) {
            ret = min(ret, cost[v][i]);
            v = anc[v][i];
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> s >> q >> e;
    for (int i = 0; i < n - 1; ++i) {
        int v, u, w;
        cin >> v >> u >> w;
        
        --v, --u;
        g[v].pb({u, w, i});
        g[u].pb({v, w, i});
    }
    for (int i = 0; i < s; ++i) {
        int v;
        cin >> v;
        --v;
        mark[v] = 1;
    }
    
    for (int i = 0; i < n; ++i) {
        mn[i] = inf;
        for (int j = 0; j < lg; ++j) {
            anc[i][j] = -1;
            cost[i][j] = inf;
        }
    }
    
    --e;
    dfs(e, e);
    calc(e, e);

    for (int i = 0; i < q; ++i) {
        int f, v;
        cin >> f >> v;
        
        --f, --v;
        int u = low[f];
            
        ll dis = cnt[v] - cnt[u];

        if (dis < 0 || up(v, dis) != u) {
            cout << "escaped\n";
        }
        else {
            ll t = ans(v, dis + 1) + d[v];
            if (t > maxa) {
                cout << "oo\n";
            }
            else {
                cout << t << '\n';
            }
        }
    }

    return 0;
}

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