Submission #1189236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189236		prism7k	Valley (BOI19_valley)	C++20	23 / 100	71 ms	14648 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][2];
int shop_node[100005][2];
int tin[100005], tout[100005];
const ll INF = 2e16+5;
int timer = 0;

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

bool is_anc(int u, int v1, int v2) {
	return (
		(tin[v1] <= tin[u] && tout[v1] >= tout[u]) && 
		(tin[v2] <= tin[u] && tout[v2] >= 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});
	}
	for(int i = 1; i <= N; ++i) dist[i][0] = dist[i][1] = INF;
	priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> q;
	for(int i = 0, c; i < S; ++i) {
		cin >> c;
		q.push({0LL, c, c});
		dist[c][0] = dist[c][1] = 0;
		shop_node[c][0] = shop_node[c][1] = c;
	}
	while(!q.empty()) {
		auto[cur_dist, u, p] = q.top(); q.pop();
		if(dist[u][1] < cur_dist) continue;
		for (auto [v, w] : adj[u]) {
			ll new_dist = cur_dist + w;
			if (new_dist < dist[v][0]) {
				dist[v][0] = new_dist;
				shop_node[v][0] = p;
				q.push({dist[v][0], v, p});
			} else if (new_dist < dist[v][1] && shop_node[v][0] != p) {
				dist[v][1] = new_dist;
				shop_node[v][1] = p;
				q.push({dist[v][1], v, p});
			}
		}
	}
	dfs(E, 0);
	for(int i = 0, I, R; i < Q; ++i) {
		cin >> I >> R;
		--I;
		int v1 = roads[I].v1, v2 = roads[I].v2;
		if(tin[v2] > tin[v1]) swap(v1, v2);
		if(!is_anc(R, v1, v2)) cout << "escaped\n";
		else {
			int shop1 = shop_node[R][0];
			int shop2 = shop_node[R][1];
			if(is_anc(shop1, v1, v2)) {
				cout << dist[R][0] << "\n";
			}
			else if(is_anc(shop2, v1, v2)) {
				cout << dist[R][1] << "\n";
			}
			else cout << "oo\n";
		}
	}
}

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