Submission #1061998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061998		manhlinh1501	Valley (BOI19_valley)	C++17	100 / 100	90 ms	37048 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using i64 = long long;
const int MAXN = 1e5 + 5;
const int LOGN = 20;
const i64 oo64 = 1e18 + 5;

struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

int N, S, Q, E;
edge e[MAXN];
vector<pii> adj[MAXN];
int shop[MAXN];
bool is_shop[MAXN];
i64 dist[MAXN];
int depth[MAXN];
int par[MAXN];
int chainID[MAXN];
int chainHead[MAXN];
int curChain = 0;
int curPos = 0;
int pos[MAXN];
int tour[MAXN];
int sz[MAXN];
int bigC[MAXN];
i64 RMQ[MAXN][LOGN];
i64 minn[MAXN];
i64 tot = 0;

void DFS(int u, int p) {
    par[u] = p;
    sz[u] = 1;
    depth[u] = depth[p] + 1;
    minn[u] = (is_shop[u] ? dist[u] : oo64);
    for(auto [v, w] : adj[u]) {
        if(v == p) continue;
        dist[v] = dist[u] + w;
        DFS(v, u);
        minn[u] = min(minn[u], minn[v]);
        sz[u] += sz[v];
        if(sz[bigC[u]] < sz[v]) bigC[u] = v;
    }
}

void HLD(int u, int p) {
    if(chainHead[curChain] == 0)
        chainHead[curChain] = u;

    chainID[u] = curChain;
    tour[++curPos] = u;
    pos[u] = curPos;

    if(bigC[u] != 0)
        HLD(bigC[u], u);

    for(auto [v, w] : adj[u]) {
        if(v == p or v == bigC[u]) continue;
        curChain++;
        HLD(v, u);
    }
}

int LCA(int u, int v) {
    while(chainID[u] != chainID[v]) {
        if(chainID[u] > chainID[v]) u = par[chainHead[chainID[u]]];
        else v = par[chainHead[chainID[v]]];
    }
    return (depth[u] < depth[v] ? u : v);
}

i64 get_dist(int u, int v) {
    return dist[u] + dist[v] - 2LL * dist[LCA(u, v)];
}

i64 get_min(int l, int r) {
    int b = 31 - __builtin_clz(r - l + 1);
    return min(RMQ[l][b], RMQ[r - (1 << b) + 1][b]);
}

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> S >> Q >> E;

    for(int i = 1; i < N; i++) {
        auto &[u, v, w] = e[i];
        cin >> u >> v >> w;
        tot += w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    for(int i = 1; i <= S; i++) {
        cin >> shop[i];
        is_shop[shop[i]] = true;
    }

    DFS(E, 0);
    HLD(E, 0);

    for(int i = 1; i < N; i++) {
        auto &[u, v, w] = e[i];
        if(depth[u] > depth[v]) swap(u, v);
    }

//    for(int i = 1; i <= N; i++) cerr << i << " " << minn[i] - 2 * dist[i] << "\n";
    for(int i = 1; i <= N; i++) RMQ[pos[i]][0] = minn[i] - 2 * dist[i];
//    for(int i = 1; i <= N; i++) cerr << tour[i] << "\n";
    for(int j = 1; j < LOGN; j++) {
        for(int i = 1; i + (1 << j) - 1 <= N; i++)
            RMQ[i][j] = min(RMQ[i][j - 1], RMQ[i + (1 << (j - 1))][j - 1]);
    }

    while(Q--) {
        int I, R;
        cin >> I >> R;
        const auto [u, v, w] = e[I];
        if(get_dist(R, v) + get_dist(u, E) + w != get_dist(R, E)) {
            cout << "escaped\n";
        } else {
//            cout << "skip\n";
            i64 ans = dist[R];
            i64 res = oo64;
            while(chainID[R] != chainID[v]) {
//                cout << pos[chainHead[chainID[R]]] << " " << pos[R] << "\n";
                res = min(res, get_min(pos[chainHead[chainID[R]]], pos[R]));
                R = par[chainHead[chainID[R]]];
            }
            res = min(res, get_min(pos[v], pos[R]));
            if(res > tot) cout << "oo";
            else cout << ans + res;
            cout << "\n";
        }
    }

    return (0 ^ 0);
}

/**
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
**/

/**
10 2 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
2 1
1 5
8 4
6 2
7 7
**/

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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