Submission #781770

#	Time	Username	Problem	Language	Result	Execution time	Memory
781770		elazarkoren	Valley (BOI19_valley)	C++17	36 / 100	3057 ms	25884 KiB

valley

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
// #define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
 
const int MAX_N = 1e5 + 5;
const ll infinity = 1e18;
const int block = 300;
const int BITS = 17;
 
vector<tuple<int, ll, int>> tree[MAX_N];
bool shop[MAX_N];   
int a[MAX_N], b[MAX_N];
ll we[MAX_N];
int dp[BITS][MAX_N];
ll depth1[MAX_N], depth2[MAX_N];
 
void DfsDepth(int node, int parent, ll d1, int d2) {
    dp[0][node] = parent;
    depth1[node] = d1, depth2[node] = d2;
    for (auto [neighbor, w, i] : tree[node]) {
        if (neighbor != parent) DfsDepth(neighbor, node, d1 + w, d2 + 1);
    }
}
 
int Lca(int a, int b) {
    if (depth2[a] < depth2[b]) swap(a, b);
    for (int i = BITS - 1; i >= 0; i--) {
        if (((depth2[a] - depth2[b]) >> i) & 1) a = dp[i][a];
    }
    if (a == b) return a;
    for (int i = BITS - 1; i >= 0; i--) {
        if (dp[i][a] != dp[i][b]) {
            a = dp[i][a], b = dp[i][b];
        }
    }
    return dp[0][a];
}
 
ll Dist(int a, int b) {
    return depth1[a] + depth1[b] - 2 * depth1[Lca(a, b)];
}
 
bool Escaped(int r, int e, int i) {
    ll d1 = Dist(r, e);
    ll d2 = min(Dist(r, a[i]) + Dist(e, b[i]), Dist(r, b[i]) + Dist(e, a[i])) + we[i];
    return d1 != d2;
}
 
int que_i[MAX_N], que_r[MAX_N];
ll closest[MAX_N];
bitset<MAX_N> visited_edges;
int close_node[block + 1][block + 1];
int component[MAX_N];
 
ll ClosestDown(int node, int comp, int parent = -1) {
    component[node] = comp;
    for (auto [neighbor, w, i] : tree[node]) {
        if (visited_edges[i] || neighbor == parent) continue;
        ll c = ClosestDown(neighbor, comp, node);
        chkmin(closest[node], c + w);
    }
    if (shop[node]) closest[node] = 0;
    return closest[node];
}
 
void ClosestUp(int node, ll c = infinity, int parent = -1) {
    chkmin(closest[node], c);
    chkmin(c, closest[node]);
    for (auto [neighbor, w, i] : tree[node]) {
        if (visited_edges[i] || neighbor == parent) continue;
        ClosestUp(neighbor, c + w, node);
    }
}
 
int last_vis[block + 1];
int comps;
 
void ClosestNode(int node, int parent = 0) {
    if (parent && component[node] != component[parent]) {
        for (int i = 0; i < comps; i++) {
            if (last_vis[i] != -1) {
                close_node[component[node]][i] = last_vis[i];
                close_node[i][component[node]] = node;
            }
        }
    }
    for (auto [neighbor, w, i] : tree[node]) {
        last_vis[component[node]] = node;
        if (neighbor != parent) ClosestNode(neighbor, node);
    }
    last_vis[component[node]] = node;
}
 
int n, s, q, e;
ll ans[MAX_N];

void Dfs(int node, int parent, ll d, int bad, vii &v) {
    v.push_back({node, d});
    for (auto [neighbor, w, i] : tree[node]) {
        if (node == a[bad] && neighbor == b[bad] || node == b[bad] && neighbor == a[bad]) continue;
        if (neighbor != parent) Dfs(neighbor, node, d + w, bad, v);
    }
}

void Solve(int le, int ri) {
    visited_edges.reset();
    for (int t = le; t < ri; t++) {
        visited_edges[que_i[t]] = 1;
    }
    fill(closest, closest + n + 1, infinity);
    fill(component, component + n + 1, 0);
    comps = 0;
    for (int i = 1; i <= n; i++) {
        if (!component[i]) {
            ClosestDown(i, ++comps);
            ClosestUp(i);
        }
    }
    for (int i = 1; i <= n; i++) component[i]--;
    fill(last_vis, last_vis + comps, -1);
    ClosestNode(1);
    for (int t = le; t < ri; t++) {
        int i = que_i[t], r = que_r[t];
        if (Escaped(r, e, i)) {
            ans[t] = -1;
            continue;
        }
        if (s == n) {
            ans[t] = 0;
            continue;
        }
        int c = component[r];
        ans[t] = closest[r];
        for (int j = 0; j < comps; j++) {
            if (j == c) continue;
            int node = close_node[c][j];
            if (Escaped(r, node, i)) {
                chkmin(ans[t], Dist(r, node) + closest[node]);
            }
        }
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> s >> q >> e;
    for (int i = 0; i < n - 1; i++) {
        a[i] = i + 1, b[i] = i + 2, we[i] = rand();
        cin >> a[i] >> b[i] >> we[i];
        tree[a[i]].push_back({b[i], we[i], i});
        tree[b[i]].push_back({a[i], we[i], i});
    }
    for (int i = 0; i < s; i++) {
        int x = rand() % n + 1;
        cin >> x;
        shop[x] = 1;
    }
    for (int t = 0; t < q; t++) {
        que_i[t] = rand() % (n - 1) + 1, que_r[t] = rand() % n + 1;
        cin >> que_i[t] >> que_r[t];
        que_i[t]--;
    }
    DfsDepth(1, 0, 0, 0);
    for (int i = 1; i < BITS; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
    for (int le = 0; le < q; le += block) {
        Solve(le, min(le + block, q));
    }
    for (int i = 0; i < q; i++) {
        cout << (ans[i] == -1 ? "escaped" : (ans[i] == infinity ? "oo" : to_string(ans[i]))) << '\n';
    }
}

Compilation message (stderr)

valley.cpp: In function 'void Dfs(int, int, ll, int, vii&)':
valley.cpp:110:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  110 |         if (node == a[bad] && neighbor == b[bad] || node == b[bad] && neighbor == a[bad]) continue;
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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