Submission #340680

#	Time	Username	Problem	Language	Result	Execution time	Memory
340680		8e7	Valley (BOI19_valley)	C++14	100 / 100	1970 ms	46116 KiB

valley

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define maxn 100005
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll inf = 1LL<<60;
vector<pair<int, ll> > adj[maxn];
bool st[maxn];
int lef[maxn], rig[maxn], anc[17][maxn];
ll mind[17][maxn];
struct edge {
	int a, b;
	ll w;
	edge(int x, int y, ll c) {
		a = x, b = y, w = c;
	}
	edge() {
		a = 0, b = 0, w = 0;
	}
};
edge ed[maxn];

ll dep[maxn], d2[maxn], seg[4 * maxn];
void init(int cur, int l, int r) {
	if (r <= l) return;
	if (r - l == 1) {
		seg[cur] = dep[l];
		return;
	}
	int mid = (l + r) / 2;
	init(cur * 2, l, mid), init(cur * 2 + 1, mid, r);
	seg[cur] = min(seg[cur * 2], seg[cur * 2 + 1]);
}
ll query(int cur, int l, int r, int ql, int qr) {
	if (r <= l || qr <= l || ql >= r) return inf;
	if (ql <= l && qr >= r) return seg[cur];
	int mid = (l + r) / 2;
	return min(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));
}
int cnt = 0;
void dfs(int n, int par, ll dis) {
	lef[n] = cnt;
	dep[cnt] = (st[n] ? dis : inf), d2[n] = dis;
	anc[0][n] = par;
	cnt++;
	for (auto v: adj[n]) {
		if (v.ff != par) {
			dfs(v.ff, n, dis + v.ss);
		}
	}
	rig[n] = cnt; //[l, r)
}
int main() {
	for (int i = 0;i < maxn;i++) mind[0][i] = inf;
	int n, s, q, e;
	cin >> n >> s >> q >> e;
	for (int i = 1;i <= n - 1;i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		ed[i] = edge(a, b, w);
		adj[a].push_back(make_pair(b, w));
		adj[b].push_back(make_pair(a, w));
	}
	for (int i = 0;i < s;i++) {
		int x;
		cin >> x;
		st[x] = 1;
	}
	dfs(e, 0, 1);
	for (int i = 1;i <= n;i++) cerr << lef[i] << " " << d2[i] << endl;
	init(1, 0, n);
	for (int i = 1;i <= n;i++) mind[0][i] = query(1, 0, n, lef[i], rig[i]) - 2 * d2[i], cerr << mind[0][i] << endl;
	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) {
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
			mind[i][j] = min(mind[i - 1][j], mind[i - 1][anc[i - 1][j]]);
		}
	}
	while (q--) {
		int ind, r, sub;
		cin >> ind >> r;
		if (anc[0][ed[ind].a] == ed[ind].b) sub = ed[ind].a;
		else sub = ed[ind].b;
		if (lef[r] >= lef[sub] && lef[r] < rig[sub]) {
			ll ans = inf;
			int cur = r;
			for (int j = 16;j >= 0;j--) {
				if (d2[anc[j][cur]] >= d2[sub]) {
					//cout << j << " " << cur << endl;
					ans = min(ans, d2[r] + mind[j][cur]);
					cur = anc[j][cur];
				}
			}
			ans = min(ans, d2[r] + mind[0][sub]);
			if (ans >= (inf>>1)) cout << "oo" << "\n";
			else cout << ans << "\n";
		} else {
			cout << "escaped\n";
		}
	}
}

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