제출 #1327395

#제출 시각아이디문제언어결과실행 시간메모리
1327395andy_vokizValley (BOI19_valley)C++20
59 / 100
159 ms16880 KiB
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);

using namespace std;
bool dfs(int i, int p, pair<int, int> snow, vector<vector<pair<int, int>>>& adj, int e, long long& dist, set<int>& shops, long long& minn){
    if(i == e){
        return true;
    }
    if(shops.count(i)){
        minn = min(minn, dist);
    }
    int ok = false;
    for(auto u : adj[i]){
        int j = u.first;
        int c = u.second;
        if(j == p){
            continue;
        }
        if((i == snow.first && j == snow.second) || (j == snow.first && i == snow.second)){
            continue;
        }
        dist += c;
        bool b = dfs(j, i, snow, adj, e, dist, shops, minn);
        if(b){
            ok = true;
        }
        dist -= c;
    }
    return ok;
}
int timer = 0;
void dfs2(int i, int p, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& tm){
    ++timer;
    tm[i].first = timer;
    for(auto u : adj[i]){
        int j = u.first;
        if(j == p){
            continue;
        }
        dfs2(j, i, adj, tm);
    }
    ++timer;
    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);
    }
    if(n <= 1005 && q <= 10005){
        for(int qw = 0; qw < q; ++qw){
            int r, vil;
            cin >> r >> vil;
            long long dist = 0;
            long long minn = LLONG_MAX;
            if(dfs(vil, -1, roads[r], adj, e, dist, shops, minn)){
                cout << "escaped\n";
            }else{
                if(minn == LLONG_MAX){
                    cout << "oo\n";
                }else{
                    cout << minn << "\n";
                }
            }
        }
    }else{
        vector<pair<int, int>> tm(n+1, {-1, -1});
        dfs2(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...