Submission #1190349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190349		qrn	Valley (BOI19_valley)	C++20	23 / 100	164 ms	94300 KiB

valley

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e18;
const intt mxN = 5e5 + 5;
const intt L = 21;

vector<vector<pair<intt,intt>>> graph, mn;
vector<vector<intt>>  up;
vector<intt> in(mxN), out(mxN), sub(mxN), depth(mxN), is(mxN), cost(mxN);
vector<pair<intt,intt>> H(mxN);
intt N, S, Q, E, timer;

void dfs(intt node, intt parent){
	in[node] = timer++;
	up[0][node] = parent;
	for(intt i = 1; i < L; i++) {
		up[i][node] = up[i-1][up[i-1][node]];
	}

	for(auto u : graph[node]) {
		if(u.fi != parent) {
			depth[u.fi] = depth[node] + 1;
			cost[u.fi] = cost[node] + u.se;
			dfs(u.fi, node);
		}
	}
	out[node] = timer++;
	if(is[node]) {
		H[node].fi = 0;
		H[node].se = node;
	} else {
		for(auto u : graph[node]) {
			if(u.fi != parent) {
				if(H[node].fi > H[u.fi].fi + u.se) {
					H[node].fi = H[u.fi].fi + u.se;
					H[node].se = H[u.fi].se;
				}
			}
		}
	}
}

bool isata(intt a, intt b) {
	return in[a] <= in[b] && out[a] >= out[b];
}

void solve() {
	cin >> N >> S >> Q >> E;
	graph.assign(N + 1, vector<pair<intt,intt>> {});
	up.assign(L, vector<intt> (N + 1, 0ll));
	mn.assign(L, vector<pair<intt,intt>> (N + 1, {inf, 0ll}));
	H.assign(N + 1, {inf, 0ll});
	vector<pair<intt,intt>> edge(N+1);
	
	for(intt i = 1; i <= N - 1; i++) {
		intt a, b, w;
		cin >> a >> b >> w;
		graph[a].pb({b, w});
		graph[b].pb({a, w});
		edge[i] = {a, b};
	}

	for(intt i = 1; i <= S; i++) {
		intt node;
		cin >> node;
		is[node] = 1;
	}

	dfs(E, E);

	for(intt i = 1; i <= N; i++) {
		if(H[i].fi < H[up[0][i]].fi) {
			mn[0][i] = H[i];
		} else {
			mn[0][i] = H[up[0][i]];
		}
	}


	for(intt j = 1; j < L; j++) {
		for(intt i = 1; i <= N; i++) {
			if(mn[j][i].fi > mn[j-1][up[j-1][i]].fi) {
				mn[j][i] = mn[j-1][up[j-1][i]];
			}
		}
	}

	while(Q--) {
		intt node, idx;
		cin >> idx >> node;
		intt a = edge[idx].fi, b = edge[idx].se;
		if(depth[a] > depth[b]) {
			swap(a, b);
		}
		
		if(!isata(b, node)) {
			cout << "escaped" << endl;
			continue;
		}
		
		if(is[node]) {
			cout << 0 << endl;
			continue;
		}

		intt yol = depth[node] - depth[b], qaldir = node, ans = inf, nod = 0;
		for(intt i = L - 1; i >= 0; i--) {
			if((1 << i) & yol) {
				intt mnod = mn[i][qaldir].se;
				intt c = (cost[node] - cost[up[i][qaldir]]) + mn[i][qaldir].fi;
				if(isata(mnod, node)) {
					c = cost[node] - cost[mnod];
				}
				if(ans > c) {
					ans = c;
					nod = i;
				}
				qaldir = up[i][qaldir];
			}
		}
		qaldir = node;
		ans = min(ans, H[node].fi);
		if(ans == inf) {	
			cout << "oo" << endl;
		} else {
			cout << ans  << endl;	
		}

	}
}

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1;
	// cin >> tst;
	while(tst--) {
		solve();
	}
}

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