Submission #1327360

#TimeUsernameProblemLanguageResultExecution timeMemory
1327360andy_vokizValley (BOI19_valley)C++20
0 / 100
144 ms13764 KiB
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);

using namespace std;
int timer = 0;
void dfs(int i, int p, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& tm){
    tm[i].first = timer;
    for(auto u : adj[i]){
        int j = u.first;
        if(j == p){
            continue;
        }
        ++timer;
        dfs(j, i, adj, tm);
    }
    tm[i].second = timer;
}
int main()
{
    fio
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    vector<vector<pair<int, int>>> adj(n+1);
    vector<pair<int, int>> roads(n+1);
    for(int i = 0; i < n-1; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
        roads[i+1] = {a, b};
    }
    set<int> shops;
    for(int i = 0; i< s; ++i){
        int c;
        cin >> c;
        shops.insert(c);
    }
    vector<pair<int, int>> tm(n+1);
    dfs(e, -1, adj, tm);
    for(int qw = 0; qw < q; ++qw){
        int r, vil;
        cin >> r >> vil;
        pair<int, int> egde = roads[r];
        if(tm[egde.first].first >= tm[vil].first && tm[egde.first].second <= tm[vil].second && tm[egde.second].first >= tm[vil].first && tm[egde.second].second <= tm[vil].second){
            cout << 0 << "\n";
        }else{
            cout << "escaped\n";
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...