제출 #1317221

#제출 시각아이디문제언어결과실행 시간메모리
1317221vaishakhvValley (BOI19_valley)C++20
0 / 100
58 ms15936 KiB
// 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 << "oo" << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...