Submission #594670

#	Time	Username	Problem	Language	Result	Execution time	Memory
594670		AlesL0	Valley (BOI19_valley)	C++17	36 / 100	469 ms	262144 KiB

valley

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18, sINF = 1e16;

vector <ll> f, dist;
vector <int> h, open, closed;
vector <vector<ll>> bin;
vector <vector<int>> anc;
vector <vector<pair<int, int>>> g;
vector <bool> is_shop;
ll timer = 0;

void dfs(int c, vector<bool> b){
    open[c] = timer++;
    b[c] = 1;
    if (is_shop[c])f[c] = 0;
    for (auto k : g[c]){
        if (b[k.first])continue;
        h[k.first] = h[c]+1;
        dist[k.first] = dist[c]+k.second;
        anc[k.first][0] = c;
        dfs(k.first, b);
        f[c] = min(f[c], f[k.first]+k.second);
    }
    closed[c] = timer++;
}

void build(int n){
    //resize anc ecc.
    for (int i = 1; i <= n; i++)bin[i][0] = f[anc[i][0]]-dist[anc[i][0]];
    for (int j = 1; j < 9; j++){
        for (int i = 1; i <= n; i++){
            anc[i][j] = anc[anc[i][j-1]][j-1];
            bin[i][j] = min(bin[i][j-1], bin[anc[i][j-1]][j-1]);
        }
    }
}

ll query(int a, int b){
    if (a == b)return f[a];
    int x = h[a]-h[b];
    ll len = dist[a];
    ll m = f[a]-len;
    for (int i = 0; i < 9; i++){
        if (x & (1<<i)){
            m = min(m, bin[a][i]);
            a = anc[a][i];
        }
    }
    return m+len;
}

int main(){
    int n, s, q, e; cin >> n >> s >> q >> e;
    vector <pair<int, int>> edge(1);
    h.resize(n+1); dist.resize(n+1); f.resize(n+1, INF); open.resize(n+1); closed.resize(n+1); g.resize(n+1); bin.resize(n+1); anc.resize(n+1); is_shop.resize(n+1, 0);
    for (int i = 1; i <= n; i++){anc[i].resize(9); bin[i].resize(9);}
    for (int i = 0; i < n-1; i++){
        int a, b, w; cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        edge.push_back({a, b});
    }
    while (s--){
        int c; cin >> c;
        is_shop[c] = 1;
    }
    h[e] = 0; dist[e] = 0; anc[e][0] = e;
    vector<bool> boh(n+1, 0);
    dfs(e, boh);
    build(n);
    while (q--){
        int ind, r; cin >> ind >> r;
        int x = edge[ind].first;
        if (h[edge[ind].first] < h[edge[ind].second])x = edge[ind].second;
        if (!(open[r] >= open[x] && closed[r] <= closed[x]))cout << "escaped" << "\n";
        else {
            ll k = query(r, x);
            if (k >= sINF)cout << "oo" << "\n";
            else cout << k << "\n";
        }
    }
}

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