Submission #1094336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094336		anha3k25cvp	Valley (BOI19_valley)	C++17	100 / 100	250 ms	34956 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const ll inf = 7 + 1e18;

struct Segment {
    int n;
    vector <ll> tree, a;
    Segment (int _n = 0) : n(_n) {
        tree.assign(4 * n + 1, 0);
        a.assign(4 * n + 1, 0);
    }
    void pull(int node, ll val) {
        tree[node] += val;
        a[node] += val;
    }
    void push(int node) {
        if (a[node] != 0) {
            pull(2 * node, a[node]);
            pull(2 * node + 1, a[node]);
            a[node] = 0;
        }
    }
    void update(int l, int r, int node, int u, int v, ll val) {
        if (r < u || v < l || v < u)
            return;
        if (u <= l && r <= v) {
            pull(node, val);
            return;
        }
        push(node);
        int mid = (l + r) / 2;
        update(l, mid, 2 * node, u, v, val);
        update(mid + 1, r, 2 * node + 1, u, v, val);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }
    ll get(int l, int r, int node, int u, int v) {
        if (r < u || v < l || v < u)
            return inf;
        if (u <= l && r <= v)
            return tree[node];
        push(node);
        int mid = (l + r) / 2;
        return min(get(l, mid, 2 * node, u, v), get(mid + 1, r, 2 * node + 1, u, v));
    }
};

struct Edge {
    int u, v;
    ll w;
};

int n, m, q, sink, node;
vector <Edge> e;
vector <int> l, r, a;
vector <ll> ans;
vector <vector <int>> adj;
vector <vector <II>> g;
Segment f;

void dfs(int u) {
    l[u] = ++ node;
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (l[v])
            continue;
        dfs(v);
    }
    r[u] = node;
}

void dfs_update(int u) {
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (l[v] < l[u])
            continue;
        dfs_update(v);
        int lo = 1, hi = m;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (l[v] <= l[a[mid]])
                hi = mid;
            else
                lo = mid + 1;
        }
        if (l[v] <= l[a[lo]] && l[a[lo]] <= r[v]) {
            int le = lo;
            hi = m;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (l[a[mid]] <= r[v])
                    lo = mid;
                else
                    hi = mid - 1;
            }
            f.update(1, m, 1, le, lo, e[i].w);
        }
    }
}

ll get(int L, int R) {
    if (R < L)
        return inf;
    int lo = 1, hi = m;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (L <= l[a[mid]])
            hi = mid;
        else
            lo = mid + 1;
    }
    if (l[a[lo]] < L || R < l[a[lo]])
        return inf;
    int le = lo;
    hi = m;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (l[a[mid]] <= R)
            lo = mid;
        else
            hi = mid - 1;
    }
    return f.get(1, m, 1, le, lo);
}

void dfs_query(int u) {
    for (II z : g[u]) {
        int i = z.st, id = z.nd, v = e[i].v;
        if (l[v] <= l[u] && l[u] <= r[v])
            ans[id] = get(l[v], r[v]);
        else
            ans[id] = min(get(1, l[v] - 1), get(r[v] + 1, n));
    }
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (l[v] < l[u])
            continue;
        f.update(1, m, 1, 1, m, e[i].w);
        int lo = 1, hi = m, L = 0, R = -1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (l[v] <= l[a[mid]])
                hi = mid;
            else
                lo = mid + 1;
        }
        if (l[v] <= l[a[lo]] && l[a[lo]] <= r[v]) {
            L = lo;
            hi = m;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (l[a[mid]] <= r[v])
                    lo = mid;
                else
                    hi = mid - 1;
            }
            R = lo;
            f.update(1, m, 1, L, R, -e[i].w * 2);
        }
        dfs_query(v);
        f.update(1, m, 1, 1, m, -e[i].w);
        f.update(1, m, 1, L, R, e[i].w * 2);
    }
}

int check(int u, int v) {
    return l[u] <= l[v] && l[v] <= r[u];
}

bool cmp(int u, int v) {
    return l[u] < l[v];
}

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    cin >> n >> m >> q >> sink;
    e.resize(n);
    adj.resize(n + 1);
    for (int i = 1; i < n; i ++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    l.assign(n + 1, 0);
    r.assign(n + 1, 0);
    dfs(1);
    a.assign(m + 1, 0);
    for (int i = 1; i <= m; i ++)
        cin >> a[i];
    sort(a.begin() + 1, a.end(), cmp);
    f = Segment(m);
    dfs_update(1);
    for (int i = 1; i < n; i ++)
        if (l[e[i].u] > l[e[i].v])
            swap(e[i].u, e[i].v);
    g.resize(n + 1);
    ans.assign(q + 1, inf);
    for (int i = 1; i <= q; i ++) {
        int id, u;
        cin >> id >> u;
        if (check(e[id].v, u) == check(e[id].v, sink))
            ans[i] = -1;
        else
            g[u].push_back({id, i});
    }
    dfs_query(1);
    for (int i = 1; i <= q; i ++)
        if (ans[i] < 0)
            cout << "escaped\n";
        else if (ans[i] < inf)
            cout << ans[i] << '\n';
        else
            cout << "oo\n";
    return 0;
}

Compilation message (stderr)

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

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