제출 #1307945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307945		shisp1	Valley (BOI19_valley)	C++20	23 / 100	78 ms	30992 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9+7;
const ll inf = 1e18;
const int N = 2e5+5;
int n,s,q,e, a[N], U[N], V[N], W[N], up[N][20], timer = 0, tin[N], tout[N];
vector<int>g[N];
void dfs(int v, int p) {
    tin[v] = ++timer;
    up[v][0] = p;
    for(int i = 1;i<20;i++) {
        up[v][i] = up[up[v][i-1]][i-1];
    }
    for(auto to:g[v]) {
        if(to == p) continue;
        dfs(to,v);
    }
    tout[v] = timer;
}
bool check(int a, int b) {
    return tin[a]<=tin[b] && tout[a]>=tout[b];
}
int lca(int a, int b) {
    if(check(a,b)) return a;
    if(check(b,a)) return b;
    for(int k = 19;k>=0;k--) {
        if(!check(up[a][k],b)) {
            a = up[a][k];
        }
    }
    return up[a][0];
}
void solve() {
    cin >> n >> s >> q >> e;
    vector<pair<int,int>>edjes;
    for(int i = 1;i<n;i++) {
        cin >> U[i] >> V[i] >> W[i];
        g[U[i]].pb(V[i]);
        g[V[i]].pb(U[i]);
        edjes.pb({U[i],V[i]});

    }
    for(int i = 1;i<=s;i++) {
        cin >> a[i];
    }
    dfs(e,e);
    while(q--) {
        int i, r;
        cin >> i >> r;
        int u = U[i], v=V[i];
        int c = (up[v][0] == u ? v : u);
        if(check(c,r) == check(c,e)) {
            cout << "escaped\n";
        } else {
            cout << "0\n";
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--) {
        solve();
    }





    return 0;
}

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