Submission #393955

#	Time	Username	Problem	Language	Result	Execution time	Memory
393955		inventiontime	Valley (BOI19_valley)	C++17	100 / 100	714 ms	72068 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back

#define int ll

typedef long long ll;
typedef pair<int, int> ii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

const ll maxn = 1e5 + 5;
const ll inf = LLONG_MAX/2;

int N, S, Q, E;
ii road[maxn];
vii adj[maxn];
set<int> shop;
vi tin(maxn);
vi tout(maxn);
vll dist(maxn, inf);
int par[maxn][20];
ll par_w[maxn][20];
ll par_s[maxn][20];
int cnt = 0;

void dfs(int u) {
    tin[u] = cnt; cnt++;

    for(auto [v, w] : adj[u]) if(v != par[u][0]) {
        par[v][0] = u;
        par_w[v][0] = w;
        dfs(v);
        dist[u] = min(dist[u], dist[v] + w);
    }

    if(shop.count(u)) dist[u] = 0;

    tout[u] = cnt; cnt++;
}

bool is_anc(int v, int anc) {
    return tin[v] >= tin[anc] && tout[v] <= tout[anc];
}

void lifting() {
    for(int j = 1; j <= N; j++) {
        par_s[j][0] = min(par_w[j][0] + dist[par[j][0]], dist[j]);
    }

    for(int i = 1; i <= 19; i++) for(int j = 1; j <= N; j++) {
        par[j][i] = par[par[j][i-1]][i-1];
        par_w[j][i] = par_w[par[j][i-1]][i-1] + par_w[j][i-1];
        par_s[j][i] = min(par_s[j][i-1], par_s[par[j][i-1]][i-1] + par_w[j][i-1]);
    }
}

int32_t main() {
    cin >> N >> S >> Q >> E;

    int u, v, w;
    for(int i = 1; i < N; i++) {
        cin >> u >> v >> w;
        road[i] = {u, v};
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    for(int i = 0; i < S; i++) {
        cin >> v; shop.insert(v);
    }

    par[E][0] = E;
    par_w[E][0] = 0;
    dfs(E);

    lifting();

    int I, R, top;
    ll res;
    while(Q--) {
        cin >> R >> I;
        auto [u, v] = road[R];
        if(is_anc(I, u) && is_anc(I, v)) {
            top = (is_anc(u, v) ? u : v);
            int x = I;
            ll wt = 0;
            res = dist[I];
            
            for(int i = 19; i >= 0; i--) if(is_anc(par[x][i], top)) {
                res = min(res, par_s[x][i] + wt);
                wt += par_w[x][i];
                x = par[x][i];
            }

            if(res < inf) cout << res << endl;
            else cout << "oo" << endl;
        } else {
            cout << "escaped" << endl;
        }
    }

    return 0;
}

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