| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1327359 | andy_vokiz | Valley (BOI19_valley) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);
using namespace std;
int timer = 0;
dfs(int i, int p, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& tm){
tm[i].first = timer;
for(auto u : adj[i]){
int j = u.first;
if(j == p){
continue;
}
++timer;
dfs(j, i, adj, tm);
}
tm[i].second = timer;
}
int main()
{
fio
int n, s, q, e;
cin >> n >> s >> q >> e;
vector<vector<pair<int, int>>> adj(n+1);
vector<pair<int, int>> roads(n+1);
for(int i = 0; i < n-1; ++i){
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
roads[i+1] = {a, b};
}
set<int> shops;
for(int i = 0; i< s; ++i){
int c;
cin >> c;
shops.insert(c);
}
vector<pair<int, int>> tm(n+1);
dfs(e, -1, adj, tm);
for(int qw = 0; qw < q; ++qw){
int r, vil;
cin >> r >> vil;
pair<int, int> egde = roads[r];
if(tm[egde.first].first >= tm[vil].first && tm[egde.first].second <= tm[vil].second && tm[egde.second].first >= tm[vil].first && tm[egde.second].second <= tm[vil].second){
cout << 0 << "\n";
}else{
cout << "escaped\n";
}
}
return 0;
}
