제출 #1327309

#제출 시각아이디문제언어결과실행 시간메모리
1327309edga1Valley (BOI19_valley)C++20
0 / 100
56 ms12460 KiB
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;

const ll N=1e5+5;
const ll INF=1e18;
vector<pair<ll,ll>> g[N];
vector<pair<ll,ll>> roads;
ll tin[N], tout[N];
ll S[N];
ll ns,e,top,t=0;

void dfs(ll v, ll p){
    tin[v]=t;
    t++;
    for(auto u : g[v]){
        if(u.fi==p) continue;
        dfs(u.fi,v);
    }
    tout[v]=t;
    t++;
}

ll virs(int a, int b){
    if(tin[a]<tin[b] && tout[a]>tout[b]) return 1;
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,s,q;
    cin>>n>>s>>q>>top;
    for(ll i=0; i<n-1; i++){
        ll a,b,w;
        cin>>a>>b>>w;
        g[a].pb({b,w});
        g[b].pb({a,w});
        roads.pb({a,b});
    }
    for(ll i=0; i<s; i++){
        ll a; cin>>a;
        S[a]=1;
    }
    dfs(top,top);
    for(ll i=0; i<q; i++){
        ll ban,r;
        cin>>ban>>r;
        ll a=roads[ban-1].fi,b=roads[ban-1].se;
        if(virs(b,a)) swap(b,a);
        if(tin[a]<tin[r] && tout[a]>tout[r] && tout[b]>=tout[r] && tin[b]<=tin[r]) cout<<"oo\n";
        else cout<<"escaped\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...