Submission #667167

#	Time	Username	Problem	Language	Result	Execution time	Memory
667167		Kahou	Valley (BOI19_valley)	C++14	100 / 100	201 ms	26052 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 50;
int n, s, q, r, h[N], st[N], ft[N], t;
ll dis[N];
ll dp[N];
bool mark[N];
pii E[N];
vector<pii> adj[N];
vector<pii> vc[N];
ll out[N];
ll seg[N<<2];

void dfs(int u, int p) {
	st[u] = ++t;
	h[u] = h[p]+1;
	dp[u] = 1e18;
	if (mark[u]) dp[u] = 0;

	for (pii x:adj[u]) {
		int v = x.F, w = x.S;
		if (v == p) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
		dp[u] = min(dp[u], dp[v] + w);
	}
	ft[u] = t;
}

void build(int u, int tl, int tr) {
	if (tl == tr) {
		seg[u] = 1e18;
		return;
	}
	int md = (tl+tr)>>1;
	int lc = u<<1;
	int rc = u<<1|1;
	build(lc, tl, md), build(rc, md+1, tr);
	seg[u] = min(seg[lc], seg[rc]);
}
ll query(int u, int tl, int tr, int l, int r) {
	if (r < tl || tr < l) return 1e18;
	if (l <= tl && tr <= r) {
		return seg[u];
	}
	int md = (tl+tr)>>1;
	int lc = u<<1;
	int rc = u<<1|1;
	return min(query(lc, tl, md, l, r), query(rc, md+1, tr, l, r));
}
void upd(int u, int tl, int tr, int id, ll x) {
	if (tl == tr) {
		seg[u] = x;
		return;
	}
	int md = (tl+tr)>>1;
	int lc = u<<1;
	int rc = u<<1|1;
	if (id <= md) upd(lc, tl, md, id, x);
	else upd(rc, md+1, tr, id, x);
	seg[u] = min(seg[lc], seg[rc]);
}

void dfs2(int u, int p) {
	upd(1, 1, n, h[u], dp[u] - dis[u]);

	for (pii p:vc[u]) {
		int i = p.F, id= p.S;
		int v = (h[E[id].F] < h[E[id].S] ? E[id].S : E[id].F);
		if (!(st[v] <= st[u] && ft[v] >= ft[u])) {
			out[i] = -1;
			continue;
		}
		
		out[i] = query(1, 1, n, h[v], h[u]) + dis[u];
	}

	for (pii x:adj[u]) {
		int v = x.F;
		if (v==p) continue;
		dfs2(v, u);
	}
	upd(1, 1, n, h[u], 1e18);
}

void solve() {
	cin >> n >> s >> q >> r;
	for (int i = 1; i <= n-1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		E[i] = {u, v};
	}
	for (int i = 1; i <= s; i++) {
		int u;
		cin >> u;
		mark[u] = 1;
	}
	for (int i = 1; i <= q; i++) {
		int id, u;
		cin >> id >> u;
		vc[u].push_back({i, id});
	}
	dfs(r,0);

	build(1,1,n);
	dfs2(r,0);

	for (int i = 1; i <= q; i++) {
		if (out[i] == -1) cout << "escaped" << endl;
		else if (out[i] >= 1e18) cout << "oo" << endl;
		else cout << out[i] << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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