Submission #1217599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217599		BuiDucManh123	Two Currencies (JOI23_currencies)	C++20	100 / 100	391 ms	33264 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 200005;
const int LOGN = 20;

struct Edge { int u, v; };

int n, m, q;
Edge ee[MAXN];
vector<int> g[MAXN];
int tin[MAXN], tout[MAXN], timerDFS;
int up[LOGN][MAXN];
int depthArr[MAXN];

struct Fenwick {
    int n;
    vector<ll> bit;
    Fenwick() {}
    Fenwick(int _n) { init(_n); }
    void init(int _n) {
        n = _n;
        bit.assign(n + 2, 0);
    }
    void update(int i, ll v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    // add v vào [l..r]
    void range_add(int l, int r, ll v) {
        if (l > r) return;
        update(l, v);
        if (r + 1 <= n) update(r + 1, -v);
    }
    ll point_get(int i) const {
        ll s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
} fenw;

void dfs(int u, int p) {
    tin[u] = ++timerDFS;
    up[0][u] = (p == -1 ? u : p);
    depthArr[u] = (p == -1 ? 0 : depthArr[p] + 1);
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    tout[u] = timerDFS;
}

int lca(int u, int v) {
    if (depthArr[u] < depthArr[v]) swap(u, v);
    int diff = depthArr[u] - depthArr[v];
    for (int k = 0; k < LOGN; k++) {
        if (diff & (1 << k)) {
            u = up[k][u];
        }
    }
    if (u == v) return u;
    for (int k = LOGN - 1; k >= 0; k--) {
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u];
}

struct Item {
    int v;
    ll c;
} items[MAXN];

vector<int> orig_s, orig_t, orig_x_int, orig_y_int;
vector<ll> orig_x, orig_y;
vector<int> ansIndex;

struct RecQ {
    int id, s, t, lca;
    ll y;
};

ll path_sum_cost(const RecQ* qr) {
    int s = qr->s, t = qr->t, lc = qr->lca;
    return fenw.point_get(tin[s]) + fenw.point_get(tin[t]) - 2 * fenw.point_get(tin[lc]);
}

void solve_rec(int l, int r, vector<RecQ*>& vec) {
    if (vec.empty()) return;
    if (l > r) {
        for (RecQ* p : vec) {
            ansIndex[p->id] = 0;
        }
        return;
    }
    if (l == r) {
        for (RecQ* p : vec) {
            ansIndex[p->id] = l;
        }
        return;
    }
    int mid = (l + r) / 2 + 1;
    for (int i = l + 1; i <= mid; i++) {
        int u = items[i].v;
        fenw.range_add(tin[u], tout[u], items[i].c);
    }
    vector<RecQ*> left, right;
    left.reserve(vec.size());
    right.reserve(vec.size());
    for (RecQ* p : vec) {
        ll sumc = path_sum_cost(p);
        if (p->y < sumc) {
            left.push_back(p);
        } else {
            right.push_back(p);
        }
    }
    if (!right.empty()) {
        solve_rec(mid, r, right);
    }
    for (int i = l + 1; i <= mid; i++) {
        int u = items[i].v;
        fenw.range_add(tin[u], tout[u], -items[i].c);
    }
    if (!left.empty()) {
        solve_rec(l, mid - 1, left);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n - 1; i++) {
        cin >> ee[i].u >> ee[i].v;
        g[ee[i].u].push_back(ee[i].v);
        g[ee[i].v].push_back(ee[i].u);
    }
    timerDFS = 0;
    dfs(1, -1);
    for (int k = 1; k < LOGN; k++) {
        for (int u = 1; u <= n; u++) {
            up[k][u] = up[k - 1][ up[k - 1][u] ];
        }
    }
    for (int i = 1; i <= m; i++) {
        int eid; ll c;
        cin >> eid >> c;
        int u = ee[eid].u, v = ee[eid].v;
        if (depthArr[u] < depthArr[v]) swap(u, v);
        items[i].v = u;
        items[i].c = c;
    }
    sort(items + 1, items + m + 1, [&](const Item &a, const Item &b) {
        return a.c < b.c;
    });
    orig_s.resize(q);
    orig_t.resize(q);
    orig_x.resize(q);
    orig_y.resize(q);
    vector<RecQ> recq(q);
    for (int i = 0; i < q; i++) {
        int s, t; ll x, y;
        cin >> s >> t >> x >> y;
        orig_s[i] = s;
        orig_t[i] = t;
        orig_x[i] = x;
        orig_y[i] = y;
        recq[i].id = i;
        recq[i].s = s;
        recq[i].t = t;
        recq[i].lca = lca(s, t);
        recq[i].y = y;
    }
    vector<RecQ*> vec;
    vec.reserve(q);
    for (int i = 0; i < q; i++) {
        vec.push_back(&recq[i]);
    }
    fenw.init(n);
    ansIndex.assign(q, 0);
    solve_rec(0, m, vec);
    vector<int> order(q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){
        return ansIndex[a] > ansIndex[b];
    });
    fenw.init(n);
    int ptr = m;
    vector<ll> finalCnt(q, 0);
    for (int idx : order) {
        int k = ansIndex[idx];
        while (ptr > k) {
            int u = items[ptr].v;
            fenw.range_add(tin[u], tout[u], 1);
            ptr--;
        }
        int s = orig_s[idx], t = orig_t[idx];
        int lc = lca(s, t);
        ll cntOnPath = fenw.point_get(tin[s]) + fenw.point_get(tin[t]) - 2 * fenw.point_get(tin[lc]);
        finalCnt[idx] = cntOnPath;
    }
    for (int i = 0; i < q; i++) {
        ll cnt = finalCnt[i];
        ll res = orig_x[i] - cnt;
        if (res < 0) cout << -1 << "\n";
        else cout << res << "\n";
    }
    return 0;
}

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