Submission #1116488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116488		stdfloat	Valley (BOI19_valley)	C++17	23 / 100	176 ms	22312 KiB

valley

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

using ll = long long;

int tim;

vector<bool> vis;

vector<int> d, tin, tout, sz, pr, ch;

vector<ll> v, dis1, dis2;

vector<vector<pair<int, int>>> E;

void dfs(int x, int p = -1) {
	tin[x] = tim++;
	if (~p) d[x] = d[p] + 1;

	for (auto [i, w] : E[x]) {
		if (i != p) {
			dfs(i, x);

			v[x] = min(v[x], v[i] + w);
		}
	}

	tout[x] = tim++;
}

int dfs_sz(int x, int p = -1) {
	sz[x] = 1;
	for (auto [i, w] : E[x])
		if (!vis[i] && i != p) sz[x] += dfs_sz(i, x);

	return sz[x];
}

int fnd(int x, int n, int p = -1) {
	for (auto [i, w] : E[x])
		if (!vis[i] && i != p && sz[i] > (n >> 1)) return fnd(i, n, x);

	return x;
}

void dfs_dis(int x, int c, int cp, int p = -1, ll ds = 0) {
	for (auto [i, w] : E[x]) {
		if (vis[i]) {
			if (i == cp) dis1[c] = dis2[cp] = ds + w;
		}
		else if (i != p) dfs_dis(i, c, cp, x, ds + w);
	}
}

void f(int x, int p = -1) {
	int n = dfs_sz(x), c = fnd(x, n);

	pr[c] = p;
	if (~p) {
		ch[p] = c;
		dfs_dis(c, c, p);
	}

	vis[c] = true;
	for (auto [i, w] : E[c])
		if (!vis[i]) f(i, c);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, s, q, e;
	cin >> n >> s >> q >> e; e--;

	E.assign(n, {});
	vector<int> eu(n - 1), ev(n - 1), ew(n - 1);
	for (int i = 0; i < n - 1; i++) {
		cin >> eu[i] >> ev[i] >> ew[i]; eu[i]--; ev[i]--;

		E[eu[i]].push_back({ev[i], ew[i]});
		E[ev[i]].push_back({eu[i], ew[i]});
	}

	v.assign(n, (ll)1e18);
	while (s--) {
		int x;
		cin >> x; x--;

		v[x] = 0;
	}

	d.assign(n, 0);
	sz.assign(n, 0);
	pr.assign(n, 0);
	ch.assign(n, -1);
	tin.assign(n, 0);
	tout.assign(n, 0);
	dis1.assign(n, 0);
	dis2.assign(n, 0);
	vis.assign(n, false);
	dfs(e);

	for (int i = 0; i < n - 1; i++)
		if (d[eu[i]] > d[ev[i]]) swap(eu[i], ev[i]);

	f(0);

	while (q--) {
		int ind, x;
		cin >> ind >> x; ind--; x--;

		if (!(tin[ev[ind]] <= tin[x] && tout[x] <= tout[ev[ind]])) {
			cout << "escaped\n"; continue;
		}

		ll mn = (ll)1e18, sm = 0;
		while (d[x] > d[eu[ind]]) {
			mn = min(mn, v[x] + sm);
			sm += dis1[x];
		
			if (!~pr[x]) break;
			x = pr[x];
		}


		int y = ev[ind];
		if (d[x] > d[y]) {
			vector<int> u;
			while (x != y) {
				u.push_back(y);
				y = pr[y];
			}

			while (!u.empty()) {
				sm += dis1[u.back()];
				mn = min(mn, v[u.back()] + sm);
				u.pop_back();
			}
		}

		if (mn == (ll)1e18) cout << "oo\n";
		else cout << mn << '\n';
	}
}

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