제출 #133093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133093		muradeyn	Valley (BOI19_valley)	C++14	0 / 100	446 ms	19180 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;

int par[maxx][lg] , lvl[maxx];

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

void dfs(int s,int p) {
    par[s][0] = p;
    lvl[s] = lvl[p] + 1;
    for (int i = 1;i<lg;i++)
        par[s][i] = par[par[s][i - 1]][i - 1];
    for (auto to : v[s])
        if (to.F != p) dfs(to.F , s);
}

int lca(int x,int y) {
    if (lvl[x] < lvl[y])swap(x , y);
    int diff = lvl[x] - lvl[y];
    for (int i = 0;i<lg;i++)
        if ((1 << i) & diff)x = par[x][i];
    if (x == y)return x;
    for (int i = lg - 1;i>=0;i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}

bool check(int root,int child) {
    int diff = lvl[child] - lvl[root];
    if (diff < 0)return false;
    for (int i = 0;i<lg;i++)
        if (diff & (1 << i))child = par[child][i];
    return (root == child);
}

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;
        int lc = lca(r , x);
        if (check(lc , x) && check(lc , y)) {
            if (check(x , ex) && check(y , ex))cout<<0<<endl;
            else if (check(x , r) && check(y , r))cout<<0<<endl;
            else cout<<"escaped"<<endl;
        }
        else cout<<"escaped"<<endl;
    }
}

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