Submission #1190340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190340		qrn	Valley (BOI19_valley)	C++20	23 / 100	112 ms	74704 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;
vector<vector<intt>>  up, mn;
vector<intt> in(mxN), out(mxN), sub(mxN), depth(mxN), H(mxN), is(mxN), cost(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] = 0;
	} else {
		for(auto u : graph[node]) {
			if(u.fi != parent) {
				H[node] = min(H[node], H[u.fi] + u.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<intt> (N + 1, inf));
	H.assign(N + 1, inf);
	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++) {
		// cout << i << endl;
		// cout << H[i] << " : " << up[0][i] << endl;
		// cout << mn[0].size() << endl;
		mn[0][i] = min(H[i], H[up[0][i]]);
	}


	for(intt j = 1; j < L; j++) {
		for(intt i = 1; i <= N; i++) {
			mn[j][i] = min(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) {
				if(ans > mn[i][qaldir] + (cost[node] - cost[up[i][qaldir]])) {
					ans = mn[i][qaldir] + (cost[node] - cost[up[i][qaldir]]);
					nod = i;
				}
				qaldir = up[i][qaldir];
			}
		}
		qaldir = node;
		// cout << nod << " " << add << " " << yol << endl;
		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