제출 #1280743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280743		nanaseyuzuki	Valley (BOI19_valley)	C++20	100 / 100	200 ms	83156 KiB

valley

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 2e5 + 5, B = 450, nB = 3005, lg2 = 20, mbit = (1 << 20) + 1, mm = 5e3 + 5, mod = 1e6 + 3, inf = 1e18;

int n, s, q, e, st[mn], ft[mn], up[mn][20], min_val[mn][20], id[mn], d[mn], h[mn], timer = 0, dp[mn];
vector <pii> a[mn];

void pre_dfs(int u, int p){
	st[u] = ++ timer;
	for(auto [v, w] : a[u]){
		if(v == p) continue;
		up[v][0] = u;
		h[v] = h[u] + 1, d[v] = d[u] + w;
		pre_dfs(v, u);
		dp[u] = min(dp[u], dp[v] + w);
	}
	if(id[u]) dp[u] = 0;
	ft[u] = timer;
}

void build(){
	for(int v = 1; v <= n; v++) min_val[v][0] = dp[v] - d[v];
	for(int i = 1; i <= 16; i++){
		for(int v = 1; v <= n; v++){
			if(up[v][i - 1] != -1){
				up[v][i] = up[up[v][i - 1]][i - 1];
			}
			min_val[v][i] = min(min_val[up[v][i - 1]][i - 1], min_val[v][i - 1]);
		}
	}
}

int lca(int u, int v){
	if(h[u] < h[v]) swap(u, v);
	int kc = h[u] - h[v];
	for(int i = 16; i >= 0; i--){
		if(kc & (1 << i)) u = up[u][i];
	}
	if(u == v) return u;
	for(int i = 16; i >= 0; i--){
		if(up[u][i] != -1 && up[v][i] != -1 && up[u][i] != up[v][i]){
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}

int get(int u, int v){
	int ans = inf;
	for(int i = 16; i >= 0; i--){
		if(up[u][i] != -1 && h[up[u][i]] >= h[v]){
			// cout << i << ' ' << u << ' ' << min_val[u][i] << '\n';
			ans = min(ans, min_val[u][i]);
			u = up[u][i];
		}
	}
	return ans;
}

pii edge[mn];


void solve(){
    cin >> n >> s >> q >> e;
	for(int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		edge[i] = {u, v};
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
	memset(up, -1, sizeof(up));
	fill(dp, dp + mn, inf);
	fill(&min_val[0][0], &min_val[0][0] + mn * 20, inf);
	for(int i = 1; i <= s; i++){
		int u; cin >> u;
		id[u] = 1;
	}
	pre_dfs(e, 0);
	build();
	// cout << d[5] << '\n';
	for(int i = 1; i < n; i++){
		auto [u, v] = edge[i];
		if(up[v][0] == u) swap(edge[i].fi, edge[i].se);
	}
	while(q--){
		int i, r; cin >> i >> r;
		auto [u, v] = edge[i];
		if(lca(u, r) != u) cout << "escaped\n";
		else{
			int ans = min(inf, get(r, v) + d[r]);
			if(ans == inf) cout << "oo\n";
			else cout << ans << '\n';
		} 
	}
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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