// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll cap = 1e5+1;
vector<pair<ll,ll>> adj[cap];
vector<ll> parent(cap);
ll timer = 0;
vector<ll> flat(cap), start(cap), endt(cap);
void dfs(ll u, ll par){
parent[u] = par;
start[u] = timer;
flat[timer] = u;
timer++;
for (auto s: adj[u]){
if (s.first == par) continue;
dfs(s.first, u);
}
endt[u] = timer - 1;
}
bool in_subtree(ll x, ll v){
return start[v] <= start[x]&& start[x] <= endt[v];
}
bool connected(ll a, ll b, ll v){
bool ina = in_subtree(a, v);
bool inb = in_subtree(b, v);
return ina == inb;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll n, s, q, e;
cin >> n >> s >> q >> e;
vector<tuple<ll,ll,ll>> edges;
for (ll i{}; i < n-1; i++){
ll a, b, w; cin >> a >> b >> w;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
edges.push_back({a,b,w});
}
vector<ll> shops;
for (ll i{}; i < s; i++){
ll c; cin >> c;
shops.push_back(c);
}
for (ll i{}; i < q; i++){
ll I, r; cin >> I >> r;
ll u, v, w; tie(u, v, w) = edges[I-1];
if(parent[u] == v) swap(u,v);
if (connected(r,e,v)) cout << "escaped" << "\n";
else cout << 1 << "\n";
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |