oj.uz

Submission #932251

# Submission time Handle Problem Language Result Execution time Memory
932251 2024-02-23T06:35:59 Z MisterReaper Valley (BOI19_valley) C++17
0 / 100
 127 ms 46976 KB 
#include <bits/stdc++.h>
using i64 = long long;
#define int i64

constexpr int Inf = 1E14 + 5;
constexpr int N = 1E5 + 5;
constexpr int L = 20;

int par[N][L];
int dis[N][L];

void solve() {
    int n, s, q, e;
    std::cin >> n >> s >> q >> e;

    std::vector<std::array<int, 3>> edges(n - 1);
    std::vector<std::pair<int, int>> adj[n + 1];
    for(int i = 0; i < n - 1; i++) {
        std::cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
        adj[--edges[i][0]].emplace_back(--edges[i][1], edges[i][2]);
        adj[edges[i][1]].emplace_back(edges[i][0], edges[i][2]);
    }

    std::vector<int> shops(n);
    for(int i = 0; i < s; i++) {
        int x;
        std::cin >> x;
        x--;
        shops[x] = true;
    }

    int timer = 0;
    std::vector<int> tin(n), tout(n), dist(n), depth(n);
    std::function<void(int)> dfs = [&](int node) -> void {
        tin[node] = ++timer;

        for(auto [child, d] : adj[node]) {
            if(tin[child] == 0) {
                par[child][0] = node;
                depth[child] = depth[node] + 1;
                dist[child] = dist[node] + d;
                dfs(child);
            }
        }

        tout[node] = ++timer;

        return;
    };

    par[e][0] = e;
    dfs(--e);

    for(int i = 0; i < n - 1; i++) {
        auto &[u, v, d] = edges[i];
        if(depth[u] > depth[v]) {
            std::swap(u, v);
        }
    }

    std::vector<int> magic(n, -1);
    dfs = [&](int node) -> void {
        magic[node] = Inf;

        for(auto [child, d] : adj[node]) {
            if(magic[child] == -1) {
                dfs(child);
                magic[node] = std::min(magic[node], magic[child]);
            }
        }

        if(shops[node]) {
            magic[node] = std::min(magic[node], dist[node]);
        } else {
            magic[node] = std::min(magic[node], Inf);
        }

        return;
    };

    dfs(e);
    for(int node = 0; node < n; node++) {
        if(magic[node] != Inf) {
            magic[node] -= 2 * dist[node];
        }
        //std::cerr << magic[node] << " \n"[node == n - 1];

        dis[node][0] = magic[par[node][0]];
    }

    for(int lg = 1; lg < L; lg++) {
        for(int i = 0; i < n; i++) {
            par[i][lg] = par[par[i][lg - 1]][lg - 1];
            dis[i][lg] = std::min(dis[i][lg - 1], dis[par[i][lg - 1]][lg - 1]);
            //std::cerr << i << " " << lg << " || " << dis[i][lg - 1] << " " << dis[par[i][lg - 1]][lg - 1] << "\n";
        }
    }

    for(int cCc = 1; cCc <= q; cCc++) {
        int I, R;
        std::cin >> I >> R;
        I--; R--;

        int node = edges[I][1];
        //std::cerr << "query: " << cCc << " ? " << I << " " << R << " :: " << node << " -> " << tin[node] << " " << tin[R] << " " << tout[R] << " " << tout[node] << "\n";
        if(tin[node] <= tin[R] && tout[R] <= tout[node]) {
            int ans = magic[R], bef = R;
            for(int lg = L - 1; lg >= 0; lg--) {
                int nxt = par[R][lg];
                if(tin[node] <= tin[nxt] && tout[nxt] <= tout[node]) {
                    //std::cerr << "zipla: " << R << " " << lg << " -> " << nxt << " :: " << dis[R][lg] << "\n";
                    ans = std::min(ans, dis[R][lg]);
                    R = nxt;
                }
            }

            if(ans != Inf) {
                std::cout << ans + dist[bef] << "\n";
            } else {
                std::cout << "oo\n";
            }
        } else {
            std::cout << "escaped\n";
        }
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 46976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -