제출 #541871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541871		AmirElarbi	Valley (BOI19_valley)	C++14	100 / 100	249 ms	54376 KiB

valley

#include <bits/stdc++.h>

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]);	
        if(sbmn[u[0]] != oo)
    	    mn[u[0]][0] = sbmn[u[0]]-dep[u[0]];
    }
    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 = 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