제출 #1118324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118324		stdfloat	Valley (BOI19_valley)	C++17	23 / 100	238 ms	21148 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;

vector<ll> v, dis1;

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) {
	// cout << x << ' ' << c << ' ' << cp << ' ' << p << ' ' << ds << endl;
	for (auto [i, w] : E[x]) {
		if (i == p) continue;

		if (vis[i]) {
			if (i == cp) {
				// cout << c << ' ' << ds + w << endl;
				dis1[c] = ds + w;
			}
		}
		else dfs_dis(i, c, cp, x, ds + w);
	}
}

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

	// cout << "\nfx " << x << ' ' << c << ' ' << p << '\n';

	pr[c] = p;
	if (~p) 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);
	tin.assign(n, 0);
	tout.assign(n, 0);
	dis1.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--;

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

		// cout << "\nQ " << ind << ' ' << x << ' ' << y << endl;

		ll mn = (ll)1e18, prex = -1, sm = 0;
		while (d[x] > d[eu[ind]]) {
			// cout << "x " << x << ' ' << v[x] << ' ' << sm << ' ' << pr[x] << endl;

			mn = min(mn, v[x] + sm);
			sm += dis1[x];
			prex = x; x = pr[x];
		}

		x = prex;

		if (d[x] > d[y]) {
			// cout << "sad" << endl;
			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