Submission #879537

#	Time	Username	Problem	Language	Result	Execution time	Memory
879537		phongcd	Valley (BOI19_valley)	C++17	100 / 100	178 ms	57664 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 2e5 + 2;
const int M = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
 
int n, s, q, e;
ii a[N];
ll w[N], f[N], d[N];
ll h[N], up[N][20], fu[N][20];
vector <int> g[N];

void dfs(int u, int p) {
    for (int i: g[u]) {
        int v = a[i].fi ^ a[i].se ^ u;
        if (v == p) continue;

        h[v] = h[u] + 1;
        d[v] = d[u] + w[i];
        
        up[v][0] = u;
        for (int j = 1; j < M; j ++)
            up[v][j] = up[up[v][j - 1]][j - 1];

        dfs(v, u);
        f[u] = min(f[u], f[v] + w[i]);
    }
}

void dfs2(int u, int p) {
    for (int i: g[u]) {
        int v = a[i].fi ^ a[i].se ^ u;
        if (v == p) continue;
        a[i].fi = v, a[i].se = u;

        fu[v][0] = f[u] - d[u];
        for (int j = 1; j < M; j ++)
            fu[v][j] = min(fu[v][j - 1], fu[up[v][j - 1]][j - 1]);

        dfs2(v, u);
    }
}

int jump(int u, int k) {
    for (int j = 19; j >= 0; j --)
        if (k >> j & 1) u = up[u][j];
    return u;
}

bool is_anc(int u, int p) {
    return jump(u, h[u] - h[p]) == p;
}

ll get(int u, int k) {
    ll res = INF;
    for (int j = 19; j >= 0; j --)
        if (k >> j & 1)
            res = min(res, fu[u][j]), u = up[u][j];
    return res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
  
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i ++) {
        cin >> a[i].fi >> a[i].se >> w[i];
        f[i] = INF;
        g[a[i].fi].push_back(i);
        g[a[i].se].push_back(i);
    }
    f[n] = INF;
    
    for (int i = 0, u; i < s; i ++)
        cin >> u, f[u] = 0; 

    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < M; j ++) fu[i][j] = INF;

    dfs(e, 0);
    dfs2(e, 0);

    while (q --) {
        int i, r; cin >> i >> r;
        int u = a[i].fi;
        if (!is_anc(r, u)) 
            cout << "escaped\n"; 
        else if (f[u] == INF) 
            cout << "oo\n";
        else cout << min(d[r] + get(r, h[r] - h[u]), f[r]) << '\n';
    }
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

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