Submission #1245595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245595		corvus	Valley (BOI19_valley)	C++20	36 / 100	3093 ms	21996 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 100 , LOG = 20;

vector <vector <pair <int , int>>> edj;
map <pair <int , int> , int> idx;
vector <bool> vis;
bool ok = 1 , ok2 = 0;
int target ;
void dfs(int node , int nx) {
    if(vis[node] || ok2) return; vis[node] = 1;
    if(target == node) ok2 = 1;
    for(auto [w , to] : edj[node]) {
        int k = idx[{node , to}];
        if(k == nx) continue;
        // cout << k << ' ' << nx << '\n';
        dfs(to , nx);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , s , Q , e ; cin >> n >> s >> Q >> e; target = e;
    edj = vector <vector <pair <int , int>>> (n + 1);
    vector <tuple <int , int , int>> vec(n - 1);
    vis = vector <bool>(n + 1, false);
    for(int i = 0 ; i < n - 1 ; i ++) {
        int u , v , w;  cin >> u >> v >> w;
        vec[i] = {u , v , w};
        idx[{u , v}] = idx[{v , u}] = i + 1;
        edj[u].pb({w , v});
        edj[v].pb({w , u});
    }
    vector <int> shops(s);
    for(int i = 0 ; i < s ; i ++) {
        cin >> shops[i];
    }
    // for(int i = 1 ; i <= n ; i ++) cout << dist[i] << ' ';cout << '\n';
    while( Q-- ) {
        int l , r ; cin >> l >> r; ok = 1; ok2 = 0;
        fill(all(vis) , 0);
        dfs(r , l);
        if(ok2) {
            cout << "escaped\n"; continue;
        }

        queue <int> q;
        vector <ll> dist(n + 1 , (ll) 1e18);
        for(int i = 0 ; i < s ; i ++) {
            q.push(shops[i]);
            dist[shops[i]] = 0;
        }
        while(q.size()) {
            int u = q.front(); q.pop();
            for(auto [w , to] : edj[u]) {
                int k = idx[{u , to}];
                if(k == l) continue;
                // cout << 
                if(dist[to] > dist[u] + w) {
                    dist[to] = dist[u] + w;
                    q.push(to);
                }
            }
        }
        // cout << dist[r] << '\n';
        if(dist[r] == (ll)1e18) cout << "oo\n";
        else cout << dist[r] << '\n';
    }
}

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