oj.uz

Submission #140671

# Submission time Handle Problem Language Result Execution time Memory
140671 2019-08-04T11:51:37 Z Minnakhmetov Valley (BOI19_valley) C++14
100 / 100
 393 ms 34028 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()


struct E {
    int to, w;
};

const int N = 1e5 + 5;
vector<E> g[N];
vector<int>qr[N];

int hurdle[N], tin[N], tout[N], x[N], tour[N];
ll h[N], up[N * 4];
pair<int, ll> t[N * 4], ans[N];
bool isShop[N];

vector<pair<int, int>> edges;

int n, s, q, e, timer = -1;

void push(int v, int L, int R) {
    if (up[v]) {
        t[v].second += up[v];
        if (L != R) {
            up[v * 2] += up[v];
            up[v * 2 + 1] += up[v];
        }
        up[v] = 0;
    }
}

void build(int v = 1, int L = 0, int R = n - 1) {
    if (L == R) {
        if (tour[L] == e) {
            t[v] = { -1, 0 };
        }
        else if (isShop[tour[L]]) {
            t[v] = { 0, h[tour[L]] };
        }
        else {
            t[v] = { 1, 0 };
        }
    }
    else {
        int m = (L + R) >> 1;
        build(v * 2, L, m);
        build(v * 2 + 1, m + 1, R);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
}

void upd(int l, int r, ll x, int v = 1, int L = 0, int R = n - 1) {
    push(v, L, R);
    if (l > r)
        return;
    if (l == L && r == R) {
        up[v] += x;
        push(v, L, R);
    }
    else {
        int m = (L + R) >> 1;
        upd(l, min(m, r), x, v * 2, L, m);
        upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
}

pair<int, ll> que(int l, int r, int v = 1, int L = 0, int R = n - 1) {
    push(v, L, R);
    if (l > r)
        return { 1, 0 };
    if (l == L && r == R) {
        return t[v];
    }
    int m = (L + R) >> 1;
    return min(que(l, min(m, r), v * 2, L, m),
        que(max(m + 1, l), r, v * 2 + 1, m + 1, R));
}

void dfs(int node, int anc) {
    tin[node] = ++timer;
    tour[timer] = node;
    for (E e : g[node]) {
        if (e.to != anc) {
            h[e.to] = h[node] + e.w;
            dfs(e.to, node);
        }
    }
    tout[node] = timer;
}

bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void deep(int node, int anc) {
    for (int i : qr[node]) {
        if (upper(hurdle[i], node)) {
            ans[i] = que(tin[hurdle[i]], tout[hurdle[i]]);
        }
        else {
            ans[i] = min(que(0, tin[hurdle[i]] - 1), que(tout[hurdle[i]] + 1, n - 1));
        }
    }

    for (E e : g[node]) {
        if (e.to != anc) {
            upd(0, n - 1, e.w);
            upd(tin[e.to], tout[e.to], -2 * e.w);

            deep(e.to, node);

            upd(0, n - 1, -e.w);
            upd(tin[e.to], tout[e.to], 2 * e.w);
        }
    }
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s >> q >> e;
    e--;

    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a--, b--;
        g[a].push_back({ b, w });
        g[b].push_back({ a, w });
        edges.push_back({ a, b });
    }

    for (int i = 0; i < s; i++) {
        int x;
        cin >> x;
        isShop[x - 1] = 1;
    }

    dfs(0, -1);
    build(1, 0, n - 1);
    
    for (auto &p : edges) {
        if (tin[p.first] > tin[p.second])
            swap(p.first, p.second);
    }

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        hurdle[i] = edges[x - 1].second;
        qr[y - 1].push_back(i);
    }

    deep(0, -1);

    for (int i = 0; i < q; i++) {
        if (ans[i].first == -1) {
            cout << "escaped";
        }
        else if (ans[i].first == 0) {
            cout << ans[i].second;
        }
        else {
            cout << "oo";
        }
        cout << "\n";
    }


    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5496 KB Output is correct
2 Correct 10 ms 5496 KB Output is correct
3 Correct 10 ms 5540 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5496 KB Output is correct
2 Correct 10 ms 5496 KB Output is correct
3 Correct 10 ms 5540 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 9 ms 5244 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 10 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 8 ms 5240 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 26452 KB Output is correct
2 Correct 371 ms 26000 KB Output is correct
3 Correct 352 ms 25960 KB Output is correct
4 Correct 376 ms 29028 KB Output is correct
5 Correct 344 ms 27488 KB Output is correct
6 Correct 375 ms 34028 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5496 KB Output is correct
2 Correct 10 ms 5496 KB Output is correct
3 Correct 10 ms 5540 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 9 ms 5244 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 10 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 8 ms 5240 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 323 ms 26452 KB Output is correct
16 Correct 371 ms 26000 KB Output is correct
17 Correct 352 ms 25960 KB Output is correct
18 Correct 376 ms 29028 KB Output is correct
19 Correct 344 ms 27488 KB Output is correct
20 Correct 375 ms 34028 KB Output is correct
21 Correct 327 ms 25952 KB Output is correct
22 Correct 334 ms 25392 KB Output is correct
23 Correct 352 ms 25300 KB Output is correct
24 Correct 393 ms 27400 KB Output is correct
25 Correct 355 ms 31860 KB Output is correct
26 Correct 357 ms 25948 KB Output is correct
27 Correct 352 ms 25688 KB Output is correct
28 Correct 387 ms 25524 KB Output is correct
29 Correct 368 ms 28224 KB Output is correct
30 Correct 347 ms 30172 KB Output is correct
31 Correct 314 ms 25964 KB Output is correct
32 Correct 345 ms 25672 KB Output is correct
33 Correct 342 ms 25620 KB Output is correct
34 Correct 372 ms 27696 KB Output is correct
35 Correct 361 ms 31016 KB Output is correct
36 Correct 378 ms 28268 KB Output is correct