Submission #639803

#TimeUsernameProblemLanguageResultExecution timeMemory
639803milisavValley (BOI19_valley)C++14
0 / 100
214 ms82596 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:19: 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...