Submission #756734

#	Time	Username	Problem	Language	Result	Execution time	Memory
756734		Desh03	Two Currencies (JOI23_currencies)	C++17	0 / 100	1 ms	212 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>> g, e;
vector<vector<int>> up;
vector<int> in, out, euler, id, f, dep;
vector<bool> c;
set<pair<int, int>> s1, s2;
int lg, cnt;
long long sum, s;

void dfs(int u) {
    in[u] = euler.size();
    euler.push_back(u);
    for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
    for (auto [v, i] : g[u])
        if (v ^ up[0][u]) {
            up[0][v] = u;
            dep[v] = dep[u] + 1;
            id[v] = i;
            dfs(v);
        }
    out[u] = euler.size();
    euler.push_back(u);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for (int i = 0; i < lg; i++)
        if (k >> i & 1)
            u = up[i][u];
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--)
        if (up[i][u] ^ up[i][v])
            u = up[i][u], v = up[i][v];
    return up[0][u];
}

int block;

struct query {
    int l, r, g, id;
    long long s;
    bool lca;
    bool operator < (const query &q) const {
        int a = l / block, b = q.l / block;
        return a == b ? r < q.r : a < b;
    }
};

void add(int i) {
    for (auto [x, y] : e[i]) {
        if (s1.size()) {
            auto [mx, id] = *--s1.end();
            if (x < mx) {
                sum += x - mx;
                s1.insert({x, y});
                c[y] = 1;
                if (sum + mx <= s) sum += mx;
                else s1.erase(--s1.end()), s2.insert({mx, id}), ++cnt, c[id] = 0;
            } else {
                if (sum + x <= s) sum += x, c[y] = 1, s1.insert({x, y});
                else s2.insert({x, y}), ++cnt;
            }
        } else {
            if (x <= s) sum = x, s1.insert({x, y}), c[y] = 1;
            else s2.insert({x, y}), ++cnt;
        }
    }
}

void remove(int i) {
    for (auto [x, y] : e[i]) {
        if (c[y]) {
            sum -= x;
            s1.erase({x, y});
            c[y] = 0;
            if (s2.size()) {
                auto [x2, y2] = *s2.begin();
                if (sum + x2 <= s) {
                    --cnt;
                    s2.erase({x2, y2});
                    s1.insert({x2, y2});
                    sum += x2;
                }
            }
        } else {
            --cnt;
            s2.erase({x, y});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    while ((1 << lg) <= n) ++lg;
    block = sqrt(n), g.resize(n), up = vector<vector<int>> (lg, vector<int> (n)), id = dep = f = in = out = vector<int> (n), e.resize(n - 1), c.resize(m);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }
    for (int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        e[--p].push_back({c, i});
    }
    dfs(0);
    vector<query> queries(q);
    for (int i = 0; i < q; i++) {
        int u, v, g;
        long long s;
        cin >> u >> v >> g >> s;
        --u, --v;
        if (in[u] > in[v]) swap(u, v);
        int lc = lca(u, v);
        if (u == lc) queries[i].l = in[u] + 1, queries[i].r = in[v];
        else queries[i].l = out[u], queries[i].r = in[v];
        queries[i].id = i, queries[i].g = g, queries[i].s = s;
    }
    vector<int> ans(q);
    sort(queries.begin(), queries.end());
    int l = queries[0].l, r = l - 1;
    for (int i = 0; i < q; i++) {
        int l_ = queries[i].l, r_ = queries[i].r;
        s = queries[i].s;
        while (sum > s) {
            auto it = --s1.end();
            s2.insert(*it);
            sum -= (*it).first;
            s1.erase(it);
            ++cnt;
        }
        while (l > l_)
            if (f[euler[l - 1]]++) remove(id[euler[--l]]);
            else add(id[euler[--l]]);
        while (r < r_)
            if (f[euler[r + 1]]++) remove(id[euler[++r]]);
            else add(id[euler[++r]]);
        while (l < l_)
            if (--f[euler[l]]) add(id[euler[l++]]);
            else remove(id[euler[l++]]);
        while (r > r_)
            if (--f[euler[r]]) add(id[euler[r--]]);
            else remove(id[euler[r--]]);
        ans[queries[i].id] = cnt > queries[i].g ? -1 : cnt;
    }
    for (int v : ans) cout << v << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32