oj.uz

Submission #653625

# Submission time Handle Problem Language Result Execution time Memory
653625 2022-10-27T12:49:25 Z Eae02 Valley (BOI19_valley) C++17
23 / 100
 351 ms 19724 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 17040 KB Output is correct
2 Correct 341 ms 16972 KB Output is correct
3 Correct 351 ms 17168 KB Output is correct
4 Correct 326 ms 18320 KB Output is correct
5 Correct 345 ms 18388 KB Output is correct
6 Correct 343 ms 19724 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 404 KB Output isn't correct
2 Halted 0 ms 0 KB -