Submission #672555

#	Time	Username	Problem	Language	Result	Execution time	Memory
672555		_martynas	Valley (BOI19_valley)	C++11	100 / 100	248 ms	50960 KiB

valley

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 1e5+5;
const int MXK = 16;
const ll INF = 1e15;

int n, s, q, e;
vector<tuple<int, int, ll>> E = {{}};
vector<pil> adj[MXN];
bool shop[MXN];
int BL[MXK][MXN];
ll BL_w[MXK][MXN];
ll BL_dp[MXK][MXN];
int H[MXN];
ll dp[MXN];

void dfs(int u, int p) {
    dp[u] = (shop[u] ? 0 : INF);
    for(auto edge : adj[u]) {
        int v = edge.F;
        if(v == p) continue;
        BL[0][v] = u;
        BL_w[0][v] = edge.S;
        H[v] = H[u]+1;
        dfs(v, u);
        dp[u] = min(dp[u], dp[v]+edge.S); // dp going down the subtree
    }
}

int main() {
    FASTIO();

    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; i++) {
        int a, b, w; cin >> a >> b >> w;
        E.PB({a, b, w});
        adj[a].PB({b, w});
        adj[b].PB({a, w});
    }
    for(int i = 0; i < s; i++) {
        int j; cin >> j; shop[j] = true;
    }
    dfs(e, -1);
    BL[0][e] = e;
    for(int i = 1; i <= n; i++) {
        BL_dp[0][i] = min(dp[i], dp[BL[0][i]]+BL_w[0][i]);
    }
    for(int k = 1; k < MXK; k++) {
        for(int i = 1; i <= n; i++) {
            BL[k][i] = BL[k-1][BL[k-1][i]];
            BL_w[k][i] = BL_w[k-1][i]+BL_w[k-1][BL[k-1][i]];
            BL_dp[k][i] = min(BL_dp[k-1][i], BL_dp[k-1][BL[k-1][i]]+BL_w[k-1][i]);
        }
    }

    for(int qq = 0; qq < q; qq++) {
        int i, r; cin >> i >> r;
        // 1. binary lift to check if i-th edge is the one needed to take to reach the root
        // 2. if yes, check dp for minimal distance to shop(?)
        int u = H[get<0>(E[i])] > H[get<1>(E[i])] ? get<0>(E[i]) : get<1>(E[i]);
        if(H[r] < H[u]) {
            cout << "escaped\n";
            continue;
        }
        int v = r;
        ll ans = dp[r];
        ll curr = 0;
        for(int k = MXK-1; k >= 0; k--)
        while(H[BL[k][v]] >= H[u]) {
            ans = min(ans, BL_dp[k][v]+curr);
            curr += BL_w[k][v];
            v = BL[k][v];
        }
        if(u != v) {
            cout << "escaped\n";
            continue;
        }
        if(ans >= INF) {
            cout << "oo\n";
        }
        else {
            cout << ans << "\n";
        }
    }
    return 0;
}

/*



*/

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