Submission #1281906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281906		ducanh0811	Valley (BOI19_valley)	C++20	100 / 100	147 ms	40984 KiB

valley

#include <bits/stdc++.h>
bool M1;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 100005
int numNode, numShop, numQuery, exitNode;
vector<pair<int, int>> g[MAXN];
bool shop[MAXN];
int par[MAXN];
int dep[MAXN];
int up[MAXN][20];
int sumShop[MAXN];
int closest[MAXN];
int sumw[MAXN];
pair<int, int> edge[MAXN];
int heavy[MAXN], child[MAXN], pos[MAXN], head[MAXN], timer = 0;

struct SMT {
    int n;
    vector<int> st;
    SMT(int _n = 0) {
        n = _n;
        st.assign((n << 2) + 5, 1e15);
    }

    void update(int id, int l, int r, int p, int val) {
        if (l == r) return st[id] = min(st[id], val), void();
        int mid = (l + r) >> 1;
        if (p <= mid) update(id << 1, l, mid, p, val);
        else update(id << 1 | 1, mid + 1, r, p, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }

    void update(int p, int val) {
        update(1, 1, n, p, val);
    }

    int get(int id, int l, int r, int u, int v) {
        if (v < l || r < u) return 1e15;
        if (u <= l && r <= v) return st[id];
        int mid = (l + r) >> 1;
        return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }

    int get(int u, int v) {
        return get(1, 1, n, u, v);
    }
} tree;

///++++++++++++++++++++++++++++++++++++++///

void dfs(int u, int p) {
    sumShop[u] = shop[u];
    int mx_c = 0;
    child[u] = 1;
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (v == p) continue;
        par[v] = u;
        up[v][0] = u;
        sumw[v] = sumw[u] + w;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        child[u] += child[v];
        sumShop[u] += sumShop[v];
        if (child[v] > mx_c) {
            mx_c = child[v];
            heavy[u] = v;
        }
    }
}

void hld(int u, int h) {
    pos[u] = ++timer;
    head[u] = h;
    if (heavy[u] != 0) hld(heavy[u], h);
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (v == par[u] || v == heavy[u]) continue;
        hld(v, v);
    }
}

void prepare_LCA() {
    FOR(j, 1, 19) {
        FOR(i, 1, numNode) up[i][j] = up[up[i][j - 1]][j - 1];
    }
}

int LCA(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int h = dep[a] - dep[b];
    for (int i = 0; (1 << i) <= h; ++i) {
        if (h >> i & 1) a = up[a][i];
    }
    if (a == b) return a;
    h = __lg(dep[a]);
    for (int i = h; i >= 0; --i) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

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

void DP(int u, int p) {
    closest[u] = (shop[u] ? 0 : 1e15);
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (v == p) continue;
        DP(v, u);
        closest[u] = min(closest[u], closest[v] + w);
    }
}

int get(int u, int v) {
    int res = 1e15;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        res = min(res, tree.get(pos[head[u]], pos[u]));
        u = par[head[u]];
    }
    if (pos[u] > pos[v]) swap(u, v);
    res = min(res, tree.get(pos[u], pos[v]));
    return res;
}

void solve() {
    cin >> numNode >> numShop >> numQuery >> exitNode;
    FOR(i, 1, numNode - 1) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
        edge[i] = make_pair(u, v);
    }
    FOR(i, 1, numShop) {
        int curNode; cin >> curNode;
        shop[curNode] = true;
    }
    dfs(exitNode, 0);
    DP(exitNode, 0);
    hld(exitNode, exitNode);
    prepare_LCA();
    tree = SMT(numNode);
    FOR(i, 1, numNode) {
        tree.update(pos[i], closest[i] - sumw[i]);
    }
    FOR(i, 1, numNode - 1) {
        if (par[edge[i].first] == edge[i].second) swap(edge[i].first, edge[i].second);
    }
    FOR(Nium, 1, numQuery) {
        int I, R; cin >> I >> R;
        int u, v; tie(u, v) = edge[I];
        if (dep[R] == dep[u] + 1 + dist(v, R)) {
            if (sumShop[v] == 0) cout << "oo\n";
            else {
                cout << sumw[R] + get(v, R) << '\n';
            }
        } else cout << "escaped\n";
    }
}

///++++++++++++++++++++++++++++++++++++++///

#define task "test"
int32_t main() {
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    bool M2;
    cerr << "++++++++++++++++++++++++++++\n";
    cerr << "Time: " << clock() << "ms" << '\n';
    cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
    cerr << "++++++++++++++++++++++++++++\n";
    return 0;
}

Compilation message (stderr)

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

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