Submission #526181

#	Time	Username	Problem	Language	Result	Execution time	Memory
526181		ali22413836	Valley (BOI19_valley)	C++14	0 / 100	95 ms	17828 KiB

valley

#include <bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
ll n , s , q , e , ans ;
bool is[200009] ;
vector < pair < ll , ll > > v[200009] ;
pair < ll , ll > pr[200009] ;
ll st[200009] , en[200009]  ,cnt ;
void dfs(ll node , ll par){
    st[node] = cnt ;
    cnt++ ;
    for(auto p : v[node]){
        if(p.first == par){
            continue ;
        }
        dfs(p.first , node) ;
    }
    en[node] = cnt ;
    cnt++ ;
    return ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
    cin >> n >> s >> q >> e  ;
    e-- ;
    for(int i = 0 ; i < n - 1  ; i++){
        ll a , b , w ;
        cin >> a >> b >> w ;
        a-- , b-- ;
        pr[i] = {a , b} ;
        v[a].push_back({b , w}) ;
        v[b].push_back({a , w}) ;
    }
    for(int i = 0 ; i < s ; i++){
        ll x ;
        cin >> x ;
    }
    dfs(e , e) ;
    while(q--){
        ll l , r ;
        cin >> l >> r  ;
        l-- ;
        r-- ;
        ll f = pr[l].first ;
        if(f == e){
            f = pr[l].second ;
        }
//        cout << f << " " << r << " " << par << endl ;
        if(st[r] > st[f] && en[r] < en[f]){
            cout << 0 << endl ;
        }
        else{
            cout << "escape" << endl ;
        }
    }
    return 0 ;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41