Submission #942397

#	Time	Username	Problem	Language	Result	Execution time	Memory
942397		_callmelucian	Two Currencies (JOI23_currencies)	C++14	100 / 100	1039 ms	53512 KiB

currencies

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;

struct BIT {
    vector<ll> tr;
    BIT (int sz = 0) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int k, ll val) {
        //cerr << "update id " << k << "\n";
        for (; k < tr.size(); k += p(k)) tr[k] += val;
    }

    ll preSum (int k, ll ans = 0) {
        //cerr << "query id " << k << "\n";
        for (k; k; k -= p(k)) ans += tr[k];
        return ans;
    }

    ll query (int l, int r) { return preSum(r) - preSum(l - 1); }
};

int up[mn][18], depth[mn], sz[mn], chain[mn], szc[mn];
vector<BIT> treeSum(mn), treeCnt(mn);
pii edge[mn], cpt[mn];
vector<int> adj[mn];

/* tree DFS functions */
int preDfs (int u, int p, int d) {
    up[u][0] = p, depth[u] = d, sz[u] = 1;
    for (int i = 1; i < 18; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : adj[u])
        if (v != p) sz[u] += preDfs(v, u, d + 1);
    return sz[u];
}

bool compare (int a, int b) {
    return sz[a] > sz[b];
}

void hldDfs (int u, int p, bool toParent) {
    chain[u] = (toParent ? chain[p] : u), szc[chain[u]]++;
    sort(all(adj[u]), compare);
    bool flg = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        hldDfs(v, u, flg);
        flg = 0;
    }
}

/* LCA functions */
int goUp (int a, int k) {
    for (int i = 0; i < 18; i++)
        if (k & (1 << i)) a = up[a][i];
    return a;
}

int lca (int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = goUp(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int i = 17; i >= 0; i--)
        if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    return up[a][0];
}

/* HLD update & query functions */
int getID (int u) { return depth[u] - depth[chain[u]] + 1; }

ll getHLD (int u, int p, vector<BIT> &tree) {
    ll ans = 0;
    while (chain[u] != chain[p]) {
        ans += tree[chain[u]].preSum(getID(u));
        u = up[chain[u]][0];
    }
    return ans + tree[chain[u]].query(getID(p), getID(u));
}

void updateHLD (int u, ll delta, vector<BIT> &tree) {
    tree[chain[u]].update(getID(u), delta);
}

ll query (int u, int v, vector<BIT> &tree) {
    int lc = lca(u, v); ll ans = 0;
    if (u != lc) ans += getHLD(u, goUp(u, depth[u] - depth[lc] - 1), tree);
    if (v != lc) ans += getHLD(v, goUp(v, depth[v] - depth[lc] - 1), tree);
    return ans;
}

void update (int k, int add) {
    int c, id, u, v; tie(c, id) = cpt[k], tie(u, v) = edge[id];
    int node = (depth[u] > depth[v] ? u : v);
    updateHLD(node, c * add, treeSum);
    updateHLD(node, -add, treeCnt);
}

ll gold[mn], silver[mn], ans[mn], stateHLD;

void solve (vector<tt> qr, int l, int r) {
    int mid = ((l + r) >> 1) + 1;
    while (stateHLD < mid) update(++stateHLD, 1);
    while (stateHLD > mid) update(stateHLD--, -1);

    if (l == r) {
        // pay silver for only the first l checkpoints
        update(stateHLD--, -1);
        for (tt item : qr) {
            int u, v, id; tie(u, v, id) = item;
            ans[id] = query(u, v, treeCnt);
        }
        return;
    }

    vector<tt> toL, toR;
    for (tt item : qr) {
        int u, v, id; tie(u, v, id) = item;
        if (query(u, v, treeSum) <= silver[id]) toR.push_back(item);
        else toL.push_back(item);
    }

    if (toL.size()) solve(toL, l, mid - 1);
    if (toR.size()) solve(toR, mid, r);
}

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

    // read edges and setup HLD
    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edge[i] = {a, b};
    }
    preDfs(1, 1, 1);
    hldDfs(1, 1, 0);

    // setup BITs
    for (int i = 1; i <= n; i++) {
        if (!szc[i]) continue;
        treeSum[i] = treeCnt[i] = BIT(szc[i]);
    }

    for (int i = 1; i <= m; i++) {
        int p, c; cin >> p >> c;
        int u, v; tie(u, v) = edge[p];
        int node = (depth[u] > depth[v] ? u : v);
        updateHLD(node, 1, treeCnt);
        cpt[i] = {c, p};
    }
    sort(cpt + 1, cpt + 1 + m);

    // read queries and setup PBS
    vector<tt> qr(q);
    for (int i = 0; i < q; i++) {
        int u, v; cin >> u >> v >> gold[i] >> silver[i];
        qr[i] = make_tuple(u, v, i);
    }
    solve(qr, 0, m);

    // print final answers
    for (int i = 0; i < q; i++) {
        if (gold[i] < ans[i]) cout << -1 << "\n";
        else cout << gold[i] - ans[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

currencies.cpp: In member function 'void BIT::update(int, ll)':
currencies.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (; k < tr.size(); k += p(k)) tr[k] += val;
      |                ~~^~~~~~~~~~~
currencies.cpp: In member function 'll BIT::preSum(int, ll)':
currencies.cpp:28:14: warning: statement has no effect [-Wunused-value]
   28 |         for (k; k; k -= p(k)) ans += tr[k];
      |              ^

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