Submission #133118

#	Time	Username	Problem	Language	Result	Execution time	Memory
133118		muradeyn	Valley (BOI19_valley)	C++14	23 / 100	425 ms	17192 KiB

valley

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define fyck ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
//#define endl '\n'

using namespace std;

const int maxx = 100001 , lg = 17;

int n , m , q , ex , nxt;

int lvl[maxx] , in[maxx] , dp[maxx];

vector< pair<int,int> >v[maxx] , arr;

void dfs(int s,int p) {
    dp[s] = 1;
    in[s] = ++nxt;
    lvl[s] = lvl[p] + 1;
    for (auto to : v[s])
        if (to.F != p) dfs(to.F , s) , dp[s] += dp[to.F];
}

int x , y , w;

int main() {
    fyck
    cin>>n>>m>>q>>ex;
    for (int i = 1;i<n;i++) {
        cin>>x>>y>>w;
        v[x].push_back({y , w});
        v[y].push_back({x , w});
        arr.push_back({x , y});
    }
    for (int i = 1;i<=m;i++)cin>>x;
    dfs(1 , 0);
    int i , r;
    while (q--) {
        cin>>i>>r;
        i--;
        x = arr[i].F; y = arr[i].S;
        if (lvl[x] < lvl[y])swap(x , y);
        int res = 0;
        res += (in[r] >= in[x] && in[r] <= in[x] + dp[x] - 1);
        res += (in[ex] >= in[x] && in[ex] <= in[x] + dp[x] - 1);
        if (res & 1)cout<<0<<endl;
        else cout<<"escaped"<<endl;
    }
}

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