Submission #567448

#	Time	Username	Problem	Language	Result	Execution time	Memory
567448		_karan_gandhi	Valley (BOI19_valley)	C++17	23 / 100	134 ms	18756 KiB

valley

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

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

vector<vector<pair<int, int>>> adj;
vector<int> tin, tout;
vector<ll int> dist, dp1, dp2;
vector<bool> shop;
int timer = 0;

void dfs(int u, int par, ll int dis) {
	dist[u] = dis;
	tin[u] = timer++;

	for (auto [v, w] : adj[u]) {
		if (v == par) continue;

		dfs(v, u, dis + w);
	}

	if (shop[u]) dp1[u] = 0;
	else dp1[u] = 1e16;

	for (auto [v, _] : adj[u]) {
		if (v == par) continue;

		dp1[u] = min(dp1[u], dp1[v] + 1);
	}

	tout[u] = timer - 1;
}

bool is_acc(int acc, int child) {
	if (acc == child) return 1;
	return tin[acc] < tin[child] && tin[child] <= tout[acc];
}

void solve() {
	int n, s, q, e; cin >> n >> s >> q >> e;

	adj.resize(n);
	dp1.resize(n);
	dp2.resize(n);
	tin.resize(n);
	tout.resize(n);
	dist.resize(n);
	shop.resize(n);

	vector<pair<pair<int, int>, int>> edges;

	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		int c; cin >> c;
		a--, b--;

		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
		edges.emplace_back(make_pair(a, b), c);
	}

	for (int i = 0; i < s; i++) {
		int a; cin >> a;
		shop[a - 1] = 1;
	}

	// e is the root
	dfs(e - 1, e - 1, 0);

	// cout << pl(tin[0]) << endl;
	while (q--) {
		int a, b; cin >> a >> b;

		a--, b--;
		pair<int, int> edge = edges[a].first;
		// cout << pl(edge.first) << pl(edge.second) << pl(is_acc(edge.first, b)) << pl(is_acc(edge.second, b)) << pl(b) << endl;
		if (is_acc(edge.first, b) && is_acc(edge.second, b)) {
			cout << 0 << endl;
		} else {
			cout << "escaped" << endl;
		}
	}
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

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