Submission #140671

#	Time	Username	Problem	Language	Result	Execution time	Memory
140671		Minnakhmetov	Valley (BOI19_valley)	C++14	100 / 100	393 ms	34028 KiB

valley

#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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41