Submission #1317219

#TimeUsernameProblemLanguageResultExecution timeMemory
1317219vaishakhvValley (BOI19_valley)C++20
0 / 100
60 ms16012 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 << 1 << "\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...