Submission #653625

#	Time	Username	Problem	Language	Result	Execution time	Memory
653625		Eae02	Valley (BOI19_valley)	C++17	23 / 100	351 ms	19724 KiB

valley

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

struct edge {
	ll to;
	ll w;
};

vector<vector<edge>> adj;

vector<bool> hasShop;
vector<ll> parent;
vector<ll> dfsTravLo;
vector<ll> dfsTravHi;

vector<ll> dfsTrav;

void dfs(ll cur) {
	dfsTravLo[cur] = dfsTrav.size();
	dfsTrav.push_back(cur);
	for (edge e : adj[cur]) {
		if (e.to != parent[cur]) {
			parent[e.to] = cur;
			dfs(e.to);
		}
	}
	dfsTravHi[cur] = dfsTrav.size();
}

int main() {
	ll N, S, Q, E;
	cin >> N >> S >> Q >> E;
	E--;
	
	adj.resize(N);
	vector<pair<ll, ll>> edges(N - 1);
	for (ll i = 0; i < N - 1; i++) {
		ll a, b, w;
		cin >> a >> b >> w;
		a--; b--;
		edges[i] = { a, b };
		adj[a].push_back({ b, w });
		adj[b].push_back({ a, w });
	}
	
	hasShop.resize(N);
	for (ll i = 0; i < S; i++) {
		ll node;
		cin >> node;
		hasShop[node - 1] = true;
	}
	
	parent.resize(N, -1);
	dfsTravLo.resize(N);
	dfsTravHi.resize(N);
	dfs(E);
	
	for (auto& edge : edges)
		if (parent[edge.second] != edge.first)
			swap(edge.first, edge.second);
	
	for (ll q = 0; q < Q; q++) {
		ll blockedEdge, queryNode;
		cin >> blockedEdge >> queryNode;
		blockedEdge--;
		queryNode--;
		
		ll blockedLower = edges[blockedEdge].second;
		if (dfsTravLo[queryNode] >= dfsTravLo[blockedLower] && dfsTravHi[queryNode] <= dfsTravHi[blockedLower]) {
			cout << "0\n";
		} else {
			cout << "escaped\n";
		}
	}
}

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