제출 #1324121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324121		sh_qaxxorov_571	Valley (BOI19_valley)	C++20	100 / 100	114 ms	38504 KiB

valley

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll INF = 1e16;

struct Edge { int to, weight, id; };
vector<Edge> adj[100005];
pair<int, int> edges[100005];
int n, s, q, e_root;
bool has_shop[100005];

int tin[100005], tout[100005], timer;
ll dist[100005];
int up[100005][20];
ll best_shop[100005], dp[100005][20];

// DFS: Masofalar, LCA va Subtree oraliqlarini hisoblash
void dfs_prep(int u, int p, ll d) {
    tin[u] = ++timer;
    up[u][0] = p;
    dist[u] = d;
    best_shop[u] = (has_shop[u] ? d : INF);
    
    for (auto& edge : adj[u]) {
        if (edge.to != p) {
            dfs_prep(edge.to, u, d + edge.weight);
            best_shop[u] = min(best_shop[u], best_shop[edge.to]);
        }
    }
    tout[u] = timer;
}

// Binary Lifting uchun tayyorgarlik
void dfs_dp(int u, int p) {
    dp[u][0] = best_shop[u] - 2 * dist[u];
    for (int i = 1; i < 20; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        dp[u][i] = min(dp[u][i - 1], dp[up[u][i - 1]][i - 1]);
    }
    for (auto& edge : adj[u]) {
        if (edge.to != p) dfs_dp(edge.to, u);
    }
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s >> q >> e_root;
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w, i});
        adj[v].push_back({u, w, i});
        edges[i] = {u, v};
    }
    for (int i = 0; i < s; i++) { int c; cin >> c; has_shop[c] = true; }

    dfs_prep(e_root, e_root, 0);
    dfs_dp(e_root, e_root);

    while (q--) {
        int idx, r; cin >> idx >> r;
        int u = edges[idx].first, v = edges[idx].second;
        // Ildizga nisbatan qaysi biri pastroqda ekanini aniqlash
        int child = (dist[u] > dist[v] ? u : v);

        if (!is_ancestor(child, r)) {
            cout << "escaped\n";
        } else {
            ll res = INF;
            int curr = r;
            // Binary lifting orqali child gacha bo'lgan yo'lda eng yaqin do'konni topish
            for (int i = 19; i >= 0; i--) {
                if (is_ancestor(child, up[curr][i])) {
                    res = min(res, dp[curr][i]);
                    curr = up[curr][i];
                }
            }
            res = min(res, dp[curr][0]);
            if (res > INF / 2) cout << "oo\n";
            else cout << res + dist[r] << "\n";
        }
    }
    return 0;
}

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