Submission #859115

#	Time	Username	Problem	Language	Result	Execution time	Memory
859115		NK_	Valley (BOI19_valley)	C++17	100 / 100	200 ms	48592 KiB

valley

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

using T = array<int, 3>;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M, Q, R; cin >> N >> M >> Q >> R; --R;

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


	vi st(N), en(N), dep(N), E(N-1); vl dst(N), close(N, INFL);
	V<vl> mn(N, vl(LG, INFL)); V<vi> up(N, vi(LG));

	for(int i = 0; i < M; i++) {
		int u; cin >> u; --u; close[u] = 0;
	}

	int t = 0;
	function<void(int, int)> gen = [&](int u, int p) {
		st[u] = t++;

		for(auto& e : adj[u]) {
			auto [v, w, i] = e; if (v == p) continue;
			
			E[i] = v; dst[v] = dst[u] + w; dep[v] = dep[u] + 1;
			
			gen(v, u);

			close[u] = min(close[v] + w, close[u]);
		}
		
		en[u] = t-1;
	};

	dst[R] = dep[R] = 0; gen(R, -1);

	function<void(int, int)> dfs = [&](int u, int p) {
		mn[u][0] = close[u] - dst[u];
		up[u][0] = (p == -1 ? u : p);

		for(int i = 1; i < LG; i++) {
			up[u][i] = up[up[u][i-1]][i-1];
			mn[u][i] = min(mn[u][i-1], mn[up[u][i-1]][i-1]);
		}

		for(auto& e : adj[u]) {
			auto [v, w, i] = e; if (v == p) continue;

			dfs(v, u);
		}
	};

	dfs(R, -1);

	auto isAnc = [&](int a, int b) {
		return st[a] <= st[b] && en[b] <= en[a];
	};

	for(int i = 0; i < Q; i++) {
		int e, u; cin >> e >> u; --e, --u;
		int p = E[e];
		if (isAnc(p, u)) {
			int d = dep[u] - dep[p] + 1; ll D = dst[u], ans = INFL;

			for(int x = 0; x < LG; x++) if ((d >> x) & 1) {
				ans = min(ans, mn[u][x]);
				u = up[u][x];
			}

			ans += D;
			if (ans >= INFL) cout << "oo" << nl;
			else cout << ans << nl;

		} else cout << "escaped" << nl;
	}

	exit(0-0);
} 	 

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