Submission #639806

#	Time	Username	Problem	Language	Result	Execution time	Memory
639806		milisav	Valley (BOI19_valley)	C++14	100 / 100	300 ms	88688 KiB

valley

        #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;
          	if(a==b) return pr[a];
            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 (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:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |             for (auto [i, w, x]:node[s]) {
      |                       ^

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