Submission #526205

#	Time	Username	Problem	Language	Result	Execution time	Memory
526205		ali22413836	Valley (BOI19_valley)	C++14	23 / 100	125 ms	21096 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 , h[200009];
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 ;
    for(auto p : v[node]){
        if(p.first == par){
            continue ;
        }
        h[p.first] = h[node] + 1 ;
        dfs(p.first , node) ;
    }
    en[node] = ++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 ;
    }
    h[e] = 0  ;
    dfs(e , e) ;
    while(q--){
        ll l , r ;
        cin >> l >> r  ;
        l-- ;
        r-- ;
        ll f ;
        if(h[pr[l].first] < h[pr[l].second]){
            f = pr[l].second ;
        }
        else
            f = pr[l].first ;
//        cout << f << " " << r << " " << par << endl ;
        if(st[r] >= st[f] && en[r] <= en[f]){
            cout << 0 << endl ;
        }
        else{
            cout << "escaped" << endl ;
        }
    }
    return 0 ;
}
/*
10 10 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
1
2
3
4
5
6
7
8
9
10
2 1
1 5
8 4
6 2
7 7
5 5 3 1
1 2 3
1 3 2
3 4 1
3 5 2
1
2
3
4
5
2 2
2 5
4 5

*/

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