Submission #1189670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189670		prism7k	Valley (BOI19_valley)	C++20	0 / 100	3096 ms	14516 KiB

valley

#include <bits/stdc++.h>
using namespace std;

struct road {
	int v1, v2;
};

using ll = long long;

vector<road> roads;
vector<vector<pair<int, int>>> adj(100005);
ll dist[100005], magic[100005];
int tin[100005], tout[100005];
int jumpMagic[100005][26];
ll minMagic[100005][26];
set<int> shop_nodes;
const ll INF = 2e16+5;
const int MAXK = 25;
int timer = 0;

void dfs(int u, int p, ll d) {
	dist[u] = d;
	tin[u] = ++timer;
	for(auto[v, w] : adj[u]) {
		if(v == p) continue;
		dfs(v, u, d + w);
	}
	tout[u] = ++timer;
}

void calc_magic(int u, int p) {
	for(auto[v, w] : adj[u]) {
		if(v == p) continue;
		calc_magic(v, u);
	}
	magic[u] = INF;
	if(shop_nodes.count(u)) magic[u] = dist[u];
	for(auto[v, w] : adj[u]) {
		if(v == p) continue;
		calc_magic(v, u);
		magic[u] = min(magic[u], magic[v]);
	}
}

void lift(int u, int p) {
	minMagic[u][0] = magic[u];
	jumpMagic[u][0] = p;
	for(int k = 1; k <= MAXK; ++k) {
		jumpMagic[u][k] = jumpMagic[jumpMagic[u][k - 1]][k - 1];
		minMagic[u][k] = min(minMagic[u][k - 1], minMagic[jumpMagic[u][k - 1]][k - 1]);
	}
	for(auto [v, w] : adj[u]) {
		if(v == p) continue;
		lift(v, u);
	}
}

bool is_anc(int u, int v) {
	return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, S, Q, E; cin >> N >> S >> Q >> E; // rooted at E
	for(int i = 0, u, v, w; i < N - 1; ++i) {
		cin >> u >> v >> w;
		roads.push_back({u, v});
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs(E, 0, 0LL);
	for(int i = 0, c; i < S; ++i) {
		cin >> c;
		shop_nodes.insert(c);
	}
	magic[0] = INF;
	calc_magic(E, 0);
	for(int i = 1; i <= N; ++i) 
		if(magic[i] < INF) magic[i] -= 2 * dist[i];
	lift(E, 0);
	int I, R;
	for(int i = 0; i < Q; ++i) {
		cin >> I >> R;
		int START = R;
		--I;
		int v1 = roads[I].v1, v2 = roads[I].v2;
		if(dist[v1] < dist[v2]) swap(v1, v2);
		if(!is_anc(R, v1)) {
			cout << "escaped\n";
			continue;
		}
		ll best = magic[R];
		for(int k = MAXK; k >= 0; --k) {
			if(is_anc(jumpMagic[R][k], v1) && jumpMagic[R][k] != v1) {
				best = min(best, minMagic[R][k]);
				R = jumpMagic[R][k];
			}
		}
		best = min(best, magic[v1]);
		if(best == INF) cout << "oo\n";
		else cout << best + dist[START] << "\n";
	}
}

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