Submission #544698

#	Time	Username	Problem	Language	Result	Execution time	Memory
544698		valerikk	Valley (BOI19_valley)	C++17	100 / 100	217 ms	44300 KiB

valley

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100100;
const int K = 20;
const ll INF = 1e18;

int n, s, q, e;
int a[N], b[N];
vector<pair<ll, int>> g[N];
int c[N];
bool good[N];
int tin[N], tout[N], tt;
ll h[N];
ll d[N];
int up[K][N];
ll mn[K][N];
ll val[N];

bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

void dfs(int v) {
	tin[v] = tt++;
	d[v] = INF;
	for (auto [w, u] : g[v]) {
		if (u != up[0][v]) {
			up[0][u] = v;
			h[u] = h[v] + w;
			dfs(u);
			d[v] = min(d[v], d[u] + w);
		}
	}
	if (good[v]) {
		d[v] = 0;
	}
	val[v] = d[v] - h[v];
	tout[v] = tt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> s >> q >> e;
	--e;
	for (int i = 0; i < n - 1; ++i) {
		ll w;
		cin >> a[i] >> b[i] >> w;
		--a[i];
		--b[i];
		g[a[i]].emplace_back(w, b[i]);
		g[b[i]].emplace_back(w, a[i]);
	}
	
	for (int i = 0; i < s; ++i) {
		cin >> c[i];
		--c[i];
		good[c[i]] = true;
	}
	
	up[0][e] = e;
	dfs(e);
	
	for (int i = 0; i < n - 1; ++i) {
		if (tin[a[i]] > tin[b[i]]) {
			swap(a[i], b[i]);
		}
	}

	for (int v = 0; v < n; ++v) {
		mn[0][v] = val[up[0][v]];
	}
	for (int i = 1; i < K; ++i) {
		for (int v = 0; v < n; ++v) {
			up[i][v] = up[i - 1][up[i - 1][v]];
			mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
		}
	}

	while (q--) {
		int id, v;
		cin >> id >> v;
		--id;
		--v;

		if (!anc(b[id], v)) {
			cout << "escaped\n";
			continue;
		}

		if (d[b[id]] == INF) {
			cout << "oo\n";
			continue;
		}

		int vv = v;
		ll ans = val[v];
		for (int i = K - 1; i >= 0; --i) {
			if (anc(b[id], up[i][v])) {
				ans = min(ans, mn[i][v]);
				v = up[i][v];
			}
		}
		ans += h[vv];
		cout << ans << "\n";
	}
	return 0;
}

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