Submission #1165527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165527		trvhung	Two Currencies (JOI23_currencies)	C++20	100 / 100	1212 ms	33644 KiB

currencies

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int maxn = 1e5 + 5;
int n, m, q, cnt[maxn], l[maxn], r[maxn], A[maxn], B[maxn], L[maxn], S[maxn], T[maxn], X[maxn], curChain, curPos, sz[maxn], chainID[maxn], pos[maxn], chainHead[maxn], h[maxn], par[maxn];
vector<int> adj[maxn], queries[maxn];
ll Y[maxn];
pair<int, int> P[maxn];

void dfs(int u) {
    sz[u] = 1;
    for (int v: adj[u])
        if (v != par[u]) {
            par[v] = u;
            h[v] = h[u] + 1;
            dfs(v);
            sz[u] += sz[v];
        }
}

void hld(int u) {
    if (!chainHead[curChain]) chainHead[curChain] = u;
    chainID[u] = curChain; pos[u] = curPos++;

    int nxt = 0;
    for (int v: adj[u])
        if (v != par[u] && sz[v] > sz[nxt])
            nxt = v;

    if (nxt) hld(nxt);
    for (int v: adj[u])
        if (v != par[u] && v != nxt) {
            curChain++;
            hld(v);
        }
}

int LCA(int u, int v) {
    while (chainID[u] != chainID[v])
        if (chainID[u] > chainID[v])
            u = par[chainHead[chainID[u]]];
        else 
            v = par[chainHead[chainID[v]]];

    return h[u] < h[v] ? u : v;
}

struct BIT {
    ll bit[maxn];

    void init() {
        fill(bit + 1, bit + 1 + n, 0);
    }   

    void update(int id, int v) {
        for (; id <= n; id += id & -id)
            bit[id] += v;
    }

    ll get(int id) {
        ll res = 0;
        for (; id > 0; id -= id & -id)
            res += bit[id];
        return res;
    }

    ll getRange(int l, int r) {
        return l > r ? 0 : get(r) - get(l - 1);
    }
} BIT[2];

void update(int u, int v, int id, int val) {
    if (pos[u] < pos[v]) swap(u, v);
    BIT[id].update(pos[u], val);
}

ll get(int u, int v, int id) {
    int lca = LCA(u, v);
    ll res = 0;

    while (chainID[u] != chainID[lca]) {
        res += BIT[id].getRange(pos[chainHead[chainID[u]]], pos[u]);
        u = par[chainHead[chainID[u]]];
    }

    while (chainID[v] != chainID[lca]) {
        res += BIT[id].getRange(pos[chainHead[chainID[v]]], pos[v]);
        v = par[chainHead[chainID[v]]];
    }

    if (pos[u] > pos[v]) swap(u, v);
    res += BIT[id].getRange(pos[u] + 1, pos[v]);

    return res;
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        cin >> A[i] >> B[i];
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    curChain = curPos = 1;
    dfs(1); hld(1);

    for (int i = 1; i <= m; ++i) 
        cin >> P[i].S >> P[i].F;

    for (int i = 1; i <= q; ++i) {
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        L[i] = LCA(S[i], T[i]);
        l[i] = 0; r[i] = m;
    }

    sort(P + 1, P + 1 + m);

    while (true) {
        for (int i = 0; i <= m; ++i)
            queries[i].clear();

        bool all_answered = true;
        for (int i = 1; i <= q; ++i) {
            if (l[i] > r[i]) continue;
            all_answered = false;
            queries[(l[i] + r[i]) >> 1].push_back(i);
        }

        if (all_answered) break;

        BIT[0].init(); BIT[1].init();
        for (int i = 1; i <= m; ++i) {
            int u = A[P[i].S], v = B[P[i].S];
            update(u, v, 0, 1);
        }

        for (int i = 0; i <= m; ++i) {
            for (int j: queries[i]) {
                ll s = get(S[j], T[j], 1);
                if (s <= Y[j]) {
                    cnt[j] = get(S[j], T[j], 0);
                    l[j] = i + 1;
                } else
                    r[j] = i - 1;
            }
            if (i < m) {
                int val = P[i + 1].F;
                int u = A[P[i + 1].S], v = B[P[i + 1].S];
                update(u, v, 0, -1);
                update(u, v, 1, val);
            }
        }
    }
    
    for (int i = 1; i <= q; ++i)
        cout << max(X[i] - cnt[i], -1) << el;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

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