Submission #639801

#TimeUsernameProblemLanguageResultExecution timeMemory
639801milisavValley (BOI19_valley)C++14
0 / 100
205 ms82568 KiB
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

const int M = 3e5+5;
int d[M], up[M][40], dp[M], mn[M][40], pr[M], ok[M], dist[M];
vector<array<int, 3>> node[M];
pair<int, int> v[M];

void dfs(int s, int p, int dd = 0, int D = 0) {
    d[s] = D;
    dist[s] = dd;
    up[s][0] = p;
    dp[s] = (!ok[s])*LLONG_MAX;
    for (auto [i, w, x]:node[s]) {
        if (i != p) {
            if (v[x].first != s) swap(v[x].first, v[x].second);

            dfs(i, s, dd+w, D+1);
            dp[s] = min(dp[s], dp[i]+w*(dp[i]!=LLONG_MAX));
        }
    }

    pr[s] = dp[s]-dd*(dp[s]!=LLONG_MAX);
}

int lca(int a, int b) {
    if (d[a] < d[b]) swap(a, b);
    for (int i = 0; i <= 20; i++) if ((d[a]-d[b])&(1<<i)) a = up[a][i];

    int l = 20;
    while (a != b) {
        while (l >= 0 && up[a][l] == up[b][l]) l--;
        if (l < 0) return up[a][0];
        a = up[a][l];
        b = up[b][l];
    }
 
    return a;
}

int mnn(int a, int b) {
    int ans = LLONG_MAX;
    for (int i = 0; i < 30; i++) {
        if ((d[a]-d[b])&(1<<i)) {
            ans = min(ans, mn[a][i]);
            a = up[a][i];
        }
    } return ans;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, s, q, e;
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        node[a].push_back({b, c, i});
        node[b].push_back({a, c, i});
        v[i] = {a, b};
    }

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

    dfs(e, e);
    for (int i = 1; i <= n; i++) mn[i][0] = min(pr[i], pr[up[i][0]]);
    for (int j = 1; j <= 30; j++) {
        for (int i = 1; i <= n; i++) up[i][j] = up[up[i][j-1]][j-1];
        for (int i = 1; i <= n; i++) mn[i][j] = min(mn[i][j-1], mn[up[i][j-1]][j-1]);
    }

    while (q--) {
        int i, a;
        cin >> i >> a;
        int b = v[i].second;
      	if(d[v[i].second]<d[v[i].first]) b = v[i].first;

        if (lca(a, b) != b) cout << "escaped" << endl;
        else {
            int m = mnn(a, b);
            if (m == LLONG_MAX)  cout << "oo" << endl;
            else cout << m+dist[a] << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
valley.cpp:16:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for (auto [i, w, x]:node[s]) {
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...