Submission #1245634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245634		corvus	Valley (BOI19_valley)	C++20	59 / 100	3096 ms	31672 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 = 21;

vector <vector <pair <int , int>>> edj;
map <pair <int , int> , int> idx;
int anc[N][LOG];
vector <int> lvl;
int n , s , Q , e ; 
void dfs(int node , int par) {
    anc[node][0] = par;
    for(int i = 1 ; i < LOG ; i ++) {
        if(anc[node][i - 1] > n) continue;
        anc[node][i] = anc[anc[node][i - 1]][i - 1];
    }
    for(auto [w , to] : edj[node]) if(par != to) lvl[to] = lvl[node] + 1 , dfs(to , node);
}

int Kth(int node , int k) {
    for(int i = 0 ; i < LOG ; i ++) {
        if((k >> i) & 1) node = anc[node][i];
    }
    return node;
}

int LCA(int u , int v) {
    if(lvl[u] < lvl[v]) swap(u , v);
    u = Kth(u , lvl[u] - lvl[v]);
    if(u == v) return v;
    for(int i = LOG - 1 ; i >= 0 ; i --) {
        if(anc[u][i] != anc[v][i]) u = anc[u][i] , v = anc[v][i];
    }
    return anc[u][0];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s >> Q >> e;
    edj = vector <vector <pair <int , int>>> (n + 1);
    vector <tuple <int , int , int>> vec(n - 1); lvl = vector <int>(n + 1 , {});
    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});
    }

    dfs(e , e);
    bool vis[n + 1];
    memset(vis ,false ,sizeof vis);
    vector <int> shops(s);
    for(int i = 0 ; i < s ; i ++) {
        cin >> shops[i];
        vis[shops[i]] = 1;
    }
    while( Q-- ) {
        int l , r ; cin >> l >> r; int a , b , w;
        tie(a , b , w) = vec[l - 1];
        if(LCA(a , r) == LCA(b , r)) cout << "escaped\n";
        else  {
            if(vis[r]) cout << "0\n";
            else {
                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]) {
                        if(idx[{to , u}] == l) continue;
                        if(dist[to] > dist[u] + w) {
                            dist[to] = dist[u] + w;
                            q.push(to);
                        }
                    }
                }
                if(dist[r] != (ll) 1e18) cout << dist[r] << '\n';
                else cout << "oo\n";
            }
        }
        // cout << a << ' ' << b << ' ' << r << ' ' << LCA(a , r) << ' ' << LCA(b , r) << '\n';
    }
}

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