Submission #825470

#	Time	Username	Problem	Language	Result	Execution time	Memory
825470		Shreyan_Paliwal	Valley (BOI19_valley)	C++17	0 / 100	252 ms	44340 KiB

valley

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 100000;
const int INF = 2000000000;

int n, s, q, e; // nodes, numshops, numqueries, valleynode
vector<pair<int,int>> adj[maxn];
pair<int,int> edges[maxn];
int shop[maxn]; // is shop?
int closest[maxn]; // closest shop in subtree

int dist[maxn]; // distance to root, set


int dpth[maxn]; // depth from root, set
int bl[maxn][20]; // set
int bld[maxn][20]; // array[nd] = - 2 * dist[nd] + min(dist[shop]) for shop in subtree[dist]


void dfs(int nd, int par, int pardist, int d) {
    // set depth
    dpth[nd] = d;

    // set binary lifting
    bl[nd][0] = par;
    for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];

    // recurse dfs, set distance from root
    for (auto i : adj[nd])
        if (i.first != par) {
            dist[i.first] = dist[nd] + i.second;    
            dfs(i.first, nd, i.second, d+1);
        }
    
    // init closest shop in subtree
    closest[nd] = shop[nd] ? 0 : INF;   
    for (auto i : adj[nd])
        if (i.first != par)
            closest[nd] = min(closest[nd], i.second + closest[i.first]);

    return;
}

void dfs_bld(int nd) {
    if (closest[nd] == INF) bld[nd][0] = INF;
    else bld[nd][0] = -dist[nd] + closest[nd];
    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 != bl[nd][0])
            dfs_bld(i.first);
}

inline int jmp(int nd, int k) {
    for (int i = 19; i >= 0; i--) if ((k >> i) & 1) nd = bl[nd][i];
    return nd;
}

inline bool on_path(int nd, int nd2) {
    // checking if nd2 is on nd's path to root
    return (dpth[nd] >= dpth[nd2] && jmp(nd, dpth[nd] - dpth[nd2]) == nd2);
}

void solve() {
    cin >> n >> s >> q >> e; e--;
    for (int i = 0; i < n-1; i++) {
        int c; cin >> edges[i].first >> edges[i].second >> c;
        edges[i].first--, edges[i].second--;
        adj[edges[i].first].push_back({edges[i].second, c});
        adj[edges[i].second].push_back({edges[i].first, c});
    }

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

    dfs(e, e, 0, 0);
    dfs_bld(e);

    for (int i = 0; i < q; i++) {
        // a is edge removed, b is node to find
        int a, b; cin >> a >> b; a--, b--;

        if (dpth[edges[a].first] < dpth[edges[a].second]) 
            swap(edges[a].first, edges[a].second);

        // check if escape possible
        if (!on_path(b, edges[a].first)) {
            cout << "escaped" << endl;
            continue;
        }

        // not possible, so search
        int val = INF;
        int B = b;
        for (int i = 19; i >= 0; i--) 
            if (((dpth[edges[a].first] - dpth[b] + 1) >> i) & 1)
                val = min(val, bld[b][i]), 
                b = bl[b][i];

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

        cout << val + dist[B] << endl;
        continue;
    }

}

signed main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    // freopen("main.in", "r", stdin);
    int t; 
    // cin >> t;
    t=1;
    while(t--) solve();
    return 0;
}

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