Submission #839027

#	Time	Username	Problem	Language	Result	Execution time	Memory
839027		serifefedartar	Valley (BOI19_valley)	C++17	100 / 100	193 ms	54476 KiB

valley

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005
#define int long long

vector<vector<pair<int,int>>> graph;
bool here[MAXN];
ll tin[MAXN], tout[MAXN], depth[MAXN], val[MAXN], subTree[MAXN];
ll up[LOGN][MAXN], mn[LOGN][MAXN], depthNode[MAXN];
pair<int,int> road[MAXN];
int T = 0;
ll dfs(int node, int parent) {
	tin[node] = ++T;
	ll mn_depth = 1e17;
	if (here[node])
		mn_depth = depth[node];
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		depthNode[u.f] = depthNode[node] + 1;
		depth[u.f] = depth[node] + u.s;
		ll q = dfs(u.f, node);
		mn_depth = min(mn_depth, q);
	}
	val[node] = mn_depth-2*depth[node];
	tout[node] = ++T;
	return mn_depth;
}

void dfs2(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		up[0][u.f] = node;
		mn[0][u.f] = val[u.f];
		for (int i = 1; i < LOGN; i++) {
			up[i][u.f] = up[i-1][up[i-1][u.f]];
			mn[i][u.f] = min(mn[i-1][u.f], mn[i-1][up[i-1][u.f]]);
		}
		dfs2(u.f, node);
	}
}

signed main() {
	fast
	int N, S, Q, E, A, B, W, p;
	cin >> N >> S >> Q >> E;

	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 1; i < N; i++) {
		cin >> A >> B >> W;
		graph[A].push_back({B, W});
		graph[B].push_back({A, W});
		road[i] = {A, B};
	}
	for (int i = 0; i < S; i++) {
		cin >> p;
		here[p] = true;
	}
	dfs(E, E);
	for (int i = 0; i < LOGN; i++)
		for (int j = 0; j < MAXN; j++)
			mn[i][j] = 1e17;

	for (int i = 0; i < LOGN; i++)
		up[i][E] = E, mn[i][E] = val[E];
	dfs2(E, E); 
	
	for (int i = 1; i < N; i++) {
		if (depth[road[i].s] > depth[road[i].f])
			subTree[i] = road[i].s;
		else
			subTree[i] = road[i].f;
	}

	while (Q--) {
		int road, city;
		cin >> road >> city;
		int sT = subTree[road];

		int c = city; 
		if (tin[sT] <= tin[city] && tout[city] <= tout[sT]) {
			ll res = 1e17;
			int no_of_nodes = depthNode[city] - depthNode[sT] + 1;
			for (int i = LOGN-1; i >= 0; i--) {
				if ((1<<i) & no_of_nodes) {
					res = min(res, mn[i][city]);
					city = up[i][city];
				}
			}
			res += depth[c];

			if (res >= 1e15)
				cout << "oo\n";
			else
				cout << res << "\n";
		} else
			cout << "escaped\n";
	}
}

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