Submission #1273703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273703		phungha	Valley (BOI19_valley)	C++20	0 / 100	91 ms	30696 KiB

valley

#include <bits/stdc++.h>
using namespace std;

int n, s, q, e, lg, timer = 0, tin[100001], tout[100001], depth[100001], up[100001][17];
long long dist[100001], min_dist[100001], magic[100001][17];
pair<int, int> edge[100000];
vector<pair<int, int>> a[100001];
bool shop[100001];

void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    depth[u] = (u == e ? 0 : depth[p] + 1);  // độ sâu
    min_dist[u] = (shop[u] ? dist[u] : 1e18); // khoảng cách ngắn nhất từ nút gốc e đến 1 nút của hàng trong cây con gốc u
    for (auto [v, w]: a[u]) {
        if (v == p) continue;
        dist[v] = dist[u] + w;
        dfs(v, u);
        min_dist[u] = min(min_dist[u], min_dist[v]);
    }
    tout[u] = timer;
}

long long best_magic(int r, int u) {
    // Tìm magic nhỏ nhất của các nút trên đường đi từ r -> u. Giả sử r thuộc cây con gốc u
    long long res = 1e18;
    int d = depth[r] - depth[u];
    for (int i = lg; i >= 0; i--)
        if (((d >> i) & 1) == 1) {
            res = min(res, magic[r][i]);
            r = up[r][i];
        }
    // Hiện tại r = u => cần tính cả magic[u]
    res = min(res, magic[u][0]);
    return res;
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("test01.in", "r", stdin);
    //freopen("test01.out", "w", stdout);
    cin >> n >> s >> q >> e;
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
        edge[i] = {u, v};
    }
    memset(shop, 0, sizeof(shop));
    for (int i = 1; i <= s; i++) {
        int c;
        cin >> c;
        shop[c] = 1;
    }
    dfs(e, e);
    for (int i = 1; i <= n; i++)
        magic[i][0] = (min_dist[i] == 1e18 ? 1e18 : min_dist[i] - 2 * dist[i]);
    lg = 1;
    for (; (1 << lg) <= n; lg++);
    lg--;
    for (int j = 1; j <= lg; j++)
        for (int i = 1; i <= n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            magic[i][j] = min(magic[i][j - 1], magic[up[i][j - 1]][j - 1]);
        }
    while (q--) {
        int i, r;
        cin >> i >> r;
        int u = (depth[edge[i].first] > depth[edge[i].second] ? edge[i].first : edge[i].second);
        if (tin[r] >= tin[i] && tout[r] <= tout[i]) cout << "escaped\n";
        else {
            long long t = best_magic(r, u);
            if (t == 1e18)
                cout << "oo\n";
            else
                cout << dist[r] + t << "\n";
        }
    }
    return 0;
}

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