Submission #825715

#	Time	Username	Problem	Language	Result	Execution time	Memory
825715		Shreyan_Paliwal	Valley (BOI19_valley)	C++17	100 / 100	449 ms	52504 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 200005;
const int INF = 1LL << 60;

int n, s, q, e;

vector<pair<int,int>> adj[maxn];
pair<int,int> edges[maxn];

int dist[maxn];
int dpth[maxn];
int closest[maxn];
int shop[maxn];

int bl[maxn][20];
int bld[maxn][20];
int st[maxn], en[maxn], cur = 0;

void dfs(int nd, int par, int d) {
    st[nd] = cur++;
    dist[nd] = dist[par] + d;
    dpth[nd] = dpth[par] + 1;

    for (auto i : adj[nd])
        if (i.first != par)
            dfs(i.first, nd, i.second);

    closest[nd] = (shop[nd] ? dist[nd] : INF);
    for (auto i : adj[nd])
        if (i.first != par && closest[i.first] != INF)
            closest[nd] = min(closest[nd], closest[i.first]);
    
    en[nd] = cur++;
}

void dfs_bl(int nd, int par) {
    bl[nd][0] = par;
    bld[nd][0] = (closest[nd] == INF ? INF : closest[nd] - 2 * dist[nd]);

    for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];
    for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);

    for (auto i : adj[nd])
        if (i.first != par)
            dfs_bl(i.first, nd);
}

signed main() {
    cin >> n >> s >> q >> e; e--;

    for (int i = 0; i < n-1; i++) {
        int a, b, c; cin >> a >> b >> c; a--, b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
        edges[i] = make_pair(a, b);
    }

    for (int i = 0; i < s; i++) {
        int a; cin >> a; a--;
        shop[a] = 1;
    }

    dfs(e, e, 0);
    dfs_bl(e, e);
    
    
    for (int i = 0; i < n-1; i++)
        if (dpth[edges[i].first] < dpth[edges[i].second])
            swap(edges[i].first, edges[i].second);

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b; a--, b--;

        // can escape?
        if (!(st[edges[a].first] <= st[b] && en[b] <= en[edges[a].first])) {
            cout << "escaped" << endl;
            continue;
        }

        int cost = INF;
        int nd = b;
        for (int i = 19; i >= 0; i--)
            if (((dpth[b] - dpth[edges[a].first]) >> i) & 1)
                cost = min(cost, bld[nd][i]), 
                nd = bl[nd][i];
        cost = min(cost, bld[nd][0]);

        if (cost == INF) { cout << "oo" << endl; continue; }

        cout << cost + dist[b] << endl;
        continue;
    }

    return 0;
}

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