제출 #1139768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139768		nguyenkhangninh99	Valley (BOI19_valley)	C++20	100 / 100	190 ms	67084 KiB

valley

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

#define int long long
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1e5 + 10;

int a[maxn], h[maxn], tin[maxn], out[maxn], sz[maxn];
bool check[maxn];

pair<int, pair<int, int>> edge[maxn];
vector<pair<int, int>> g[maxn];

int timeDfs = 0;
struct Node {
    int len, mn, par;
} f[maxn][20];

void dfs(int u, int p){
    tin[u] = ++timeDfs;

    if (check[u]) sz[u] = 1;
    else f[u][0].mn = 1e18;

    for (auto [v, w]: g[u]){
        if (v == p) continue;

        h[v] = h[u] + 1;
        f[v][0].par = u;
        f[v][0].len = w;

        dfs(v, u);

        sz[u] += sz[v];
        f[u][0].mn = min(f[u][0].mn, f[v][0].mn + w);
    }
    out[u] = timeDfs;
}


void solve(){
    int n, s, q, root; cin >> n >> s >> q >> root;

    for(int i = 1; i <= n - 1; i++){
   		int u, v, w; cin >> u >> v >> w;
   		edge[i] = {u, {v, w}};
        g[u].push_back({v, w}); 
        g[v].push_back({u, w});
   	}
   	
    for(int i = 1; i <= s; i++){
        cin >> a[i];	
        check[a[i]] = true;
    }

    dfs(root, -1);

    for(int j = 1; j <= 19; j++){
        for(int i = 1; i <= n; i++){
            f[i][j].par = f[f[i][j - 1].par][j - 1].par;
            f[i][j].len = f[i][j - 1].len + f[f[i][j - 1].par][j - 1].len;
            f[i][j].mn = min(f[i][j - 1].mn, f[f[i][j - 1].par][j - 1].mn + f[i][j - 1].len);
        }
    }

    while (q--){
        int id, r; cin >> id >> r;
        int u = edge[id].fi, v = edge[id].se.fi;
        if (h[u] > h[v]) swap(u, v);
        if (tin[v] <= tin[r] && out[r] <= out[v]){
            if (!sz[v]) cout << "oo" << "\n";
            else {
                int len = 0, ans = 1e18;
                for(int i = log2(n); i >= 0; i--){
                    if (h[f[r][i].par] >= h[v]){
                        ans = min(ans, f[r][i].mn + len);
                        len += f[r][i].len;
                        r = f[r][i].par;
                    }
                }
                cout << min(ans, f[r][0].mn + len) << "\n";
            }
        }
        else cout << "escaped\n";
    }
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

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