Submission #772221

#	Time	Username	Problem	Language	Result	Execution time	Memory
772221		BhavayGoyal	Valley (BOI19_valley)	C++14	100 / 100	182 ms	56824 KiB

valley

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const int linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


// -------------------------------------------------- Main Code --------------------------------------------------

const int N = 1e5+5;
vector<pii> g[N];
int n, s, q, e, shop[N], parent[N][20], tin[N], tout[N], Time = 0, sub[N], depth[N], minimum[N][20], singleDepth[N];

void dfs(int src, int par) {
    parent[src][0] = par;
    tin[src] = ++Time;
    if (shop[src]) minimum[src][0] = depth[src];
    for (auto child : g[src]) {
        int ch = child.f, wt = child.s;
        if (ch == par) continue;
        depth[ch] = depth[src] + wt;
        singleDepth[ch] = singleDepth[src]+1;
        dfs(ch, src);
        minimum[src][0] = min(minimum[src][0], minimum[ch][0]);
    }
    tout[src] = Time;
}

int kthMin(int a, int k) {
    int ans = linf;
    for (int i = 0; i < 20; i++) {
        if (k & (1ll<<i)) {
            ans = min(ans, minimum[a][i]);
            a = parent[a][i];
        }
    }

    return ans;
}

void sol() {
    for (int i = 0; i < N; i++) minimum[i][0] = linf;
    cin >> n >> s >> q >> e;

    vii edges;
    for (int i = 1; i <= n-1; i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a].pb({b, c}); g[b].pb({a, c});
        edges.pb({a, b, c});
    }

    for (int i = 1; i <= s; i++) {int x; cin >> x; shop[x] = true;}

    dfs(e, 0);
    for (int i = 1; i <= n; i++) minimum[i][0] += (-2*(depth[i]));

    for (int j = 1; j <= n-1; j++) {
        auto i = edges[j-1];
        if (i[0] != parent[i[1]][0]) swap(i[0], i[1]);
        sub[j] = i[1];
    }

    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            parent[i][j] = parent[parent[i][j-1]][j-1];
            minimum[i][j] = min(minimum[parent[i][j-1]][j-1], minimum[i][j-1]);
        }
    }

    while (q--) {
        int root, r; cin >> root >> r;
        root = sub[root];

        if (tin[root] <= tin[r] && tout[root] >= tout[r]) {

            int ans = depth[r];

            int dis = singleDepth[r]-singleDepth[root];
            ans += kthMin(r, dis+1);

            if (ans >= 5e14) cout << "oo" << "\n";
            else cout << ans << endl;
        }
        else cout << "escaped" << endl;
    }
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

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