Submission #645082

#	Time	Username	Problem	Language	Result	Execution time	Memory
645082		mychecksedad	Valley (BOI19_valley)	C++17	100 / 100	214 ms	63312 KiB

valley

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, s, q, E, tin[N], tout[N], timer = 0, up[N][K], dep[N];
vector<bool> c(N);
vector<array<int, 2>> g[N], edges;
ll dist[N], dp[N][K], d[N];
void pre(int v, int p){
    tin[v] = timer++;
    up[v][0] = p;
    dist[v] = 1e18;
    dep[v] = dep[p] + 1;
    for(auto k: g[v]){
        if(k[0] != p){
            d[k[0]] = d[v] + k[1];
            pre(k[0], v);
            dist[v] = min(dist[v], dist[k[0]] + k[1]);
        }
    }
    
    if(c[v]) dist[v] = 0;
    tout[v] = timer++;
}

bool is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void solve(){
    cin >> n >> s >> q >> E;
    for(int i = 0; i < n - 1; ++i){
        int u, v, e; cin >> u >> v >> e;
        g[u].pb({v, e});
        g[v].pb({u, e});
        edges.pb({u, v});
    }
    for(int i = 1; i <= s; ++i){
        int x; cin >> x;
        c[x] = 1;
    }
    d[E] = dep[E] = 0;
    pre(E, E);
    for(int i = 1; i <= n; ++i) dp[i][0] = min(dist[i], dist[up[i][0]] + (d[i] - d[up[i][0]]));
    for(int j = 1; j < K; ++j){
        for(int i = 1; i <= n; ++i){
            up[i][j] = up[up[i][j - 1]][j - 1]; 
            dp[i][j] = min(dp[i][j - 1], dp[up[i][j - 1]][j - 1] + (d[i] - d[up[i][j - 1]]));
        }
    }

    for(;q--;){
        int i, v; cin >> i >> v;
        int a = edges[i - 1][0], b = edges[i - 1][1];
        if(is_ancestor(a, b)) swap(a, b);
        if(!is_ancestor(a, v)){
            cout << "escaped";
        }else{
            ll best = dist[v], cur = 0;
            for(int i = K - 1; i >= 0; --i){
                if((1<<i)&(dep[v] - dep[a])){
                    best = min(best, dp[v][i] + cur);
                    cur += d[v] - d[up[v][i]];
                    v = up[v][i];
                }
            }
            if(best == 1e18) cout << "oo";
            else cout << best;
        }
        cout << '\n';
    }      
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:92:16: warning: unused variable 'aa' [-Wunused-variable]
   92 |     int T = 1, aa;
      |                ^~

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