Submission #1111151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111151		Ghulam_Junaid	Valley (BOI19_valley)	C++17	59 / 100	3048 ms	30680 KiB

valley

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 1e5 + 10;
const int LG = 18;
const ll inf = 1e18;
 
int n, s, q, root, par[N][LG], h[N], wei[N][LG];
ll dist[N];
bool shop[N];
 
pair<int, int> edge[N];
vector<pair<int, int>> g[N];
 
void dfs(int v, int p = -1){
    dist[v] = inf;
    if (shop[v]) dist[v] = 0;
 
    for (auto [w, u] : g[v]){
        if (u == p) continue;
 
        h[u] = h[v] + 1;
        par[u][0] = v;
        wei[u][0] = w;
        for (int i = 1; i < LG; i ++){
            if (par[u][i - 1] == -1) continue;
            par[u][i] = par[par[u][i - 1]][i - 1];
            wei[u][i] = wei[u][i - 1] + wei[par[u][i - 1]][i - 1];
        }
 
        dfs(u, v);
        dist[v] = min(dist[v], dist[u] + w);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> s >> q >> root;
    for (int i = 1; i < n; i ++){
        int u, v, w;
        cin >> u >> v >> w;
 
        g[u].push_back({w, v});
        g[v].push_back({w, u});
        edge[i] = {u, v};
    }
 
    for (int i = 0; i < s; i ++){
        int v;
        cin >> v;
        shop[v] = 1;
    }
 
    dfs(root);
 
    for (int i = 0; i < q; i ++){
        int id, v;
        cin >> id >> v;
        auto [a, b] = edge[id];
 
        if (par[b][0] != a)
            swap(a, b);
 
        int d = max(0, h[v] - h[b]);
        int anc = v;
        for (int i = 0; i < LG; i ++)
            if ((1 << i) & d)
                anc = par[anc][i];
 
        if (anc != b){
            cout << "escaped\n";
            continue;
        }
 
        if (s == n){
            cout << 0 << "\n";
            continue;
        }
 
        ll cur = dist[v];
        ll sm = 0;
        // cout << v << " " << cur << endl;
        while (v != b){
            ll w = wei[v][0];
            v = par[v][0];
            sm += w;
 
            cur = min(cur, dist[v] + sm);
            // cout << v << " " << cur << endl;
        }
 
        if (cur == inf)
            cout << "oo\n";
        else
            cout << cur << "\n";
    }
}

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