제출 #546676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546676		MohamedFaresNebili	Valley (BOI19_valley)	C++14	100 / 100	235 ms	53424 KiB

valley

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
 
        using namespace std;
        
        using ll = long long;
        using ii = pair<ll, ll>;
        
        #define ff first
        #define ss second
        #define pb push_back
        #define int ll
        
        const int oo = 1e18 + 7;
        
        int n, s, q, e;
        vector<array<int, 3>> adj[100001];
        bool rem[100001], shop[100001];
        int ans = oo; bool ok = 0;
        int tin[100001], out[100001], timer;
        int dep[100001], par[100001][20], mn[100001][20], sbmn[100001];
        
        int dfs_euler(int v, int p) {
            tin[v] = timer++; par[v][0] = p;
            
            for(auto u : adj[v]) {
                if(u[0] == p) continue;
                dep[u[0]] = dep[v] + u[1];
                sbmn[v] = min(sbmn[v], dfs_euler(u[0], v) + u[1]);	
            }
            out[v] = timer - 1;
            if(shop[v]) sbmn[v] = 0;
            return sbmn[v];
        }
        
        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> s >> q >> e; e--; vector<ii> edges(n - 1);
            fill(sbmn, sbmn + 100001, oo);
            for(int l = 0; l < n; l++)
                for(int i = 0; i < 20; i++)
                    mn[l][i] = oo;
            for(int l = 0; l < n - 1; l++) {
                int u, v, w; cin >> u >> v >> w; u--; v--;
                adj[u].pb({v, w, l}); adj[v].pb({u, w, l});
                edges[l] = {u, v};
            }
            for(int l = 0; l < s; l++) {
                int u; cin >> u; u--; shop[u] = 1;
            }
            dep[e] = 0; dfs_euler(e, e); /// mn[e][0] = sbmn[e];

          	for(int l = 0; l < n; l++)
              	if(sbmn[l] != oo)
                  mn[l][0] = sbmn[l] - dep[l];
            
            for(int l = 1; l < 20; l++)
                for(int i = 0; i < n; i++){
                    par[i][l] = par[par[i][l - 1]][l - 1];
                    mn[i][l] = min(mn[i][l - 1], mn[par[i][l - 1]][l - 1]);
                }
            while(q--) {
                int r, v; cin >> r >> v; r--; v--; 
                int to = edges[r].ff, from = edges[r].ss;
                if(tin[to] < tin[from]) swap(to, from);
                if(tin[to] <= tin[v] && tin[v] <= out[to]) {
                    int ans = oo, kk = v;
                    for (int i = 19; i >= 0; --i) {
                        if(dep[par[v][i]] >= dep[to]){
                            ans = min(ans, mn[v][i]);
                            v = par[v][i];
                        }
                    }
                    ans = min(ans, mn[v][0]);
                    if(ans == oo) cout << "oo\n";
                    else cout << ans + dep[kk] << "\n";
                }
                else cout << "escaped\n";
            }
        }

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