Submission #943993

#	Time	Username	Problem	Language	Result	Execution time	Memory
943993		becaido	Two Currencies (JOI23_currencies)	C++17	100 / 100	1582 ms	91988 KiB

currencies

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int TSIZ = (__lg(SIZE) + 4) * SIZE;

int n, m, q;
pair<int, int> a[SIZE];
vector<int> adj[SIZE], op[SIZE];

struct Node {
    int cnt, ls, rs;
    ll sum;
    Node() {}
    Node(int cnt, ll sum) : cnt(cnt), sum(sum), ls(0), rs(0) {}
    Node operator + (const Node &o) const {
        return Node(cnt + o.cnt, sum + o.sum);
    }
    Node operator - (const Node &o) const {
        return Node(cnt - o.cnt, sum - o.sum);
    }
} node[TSIZ];

int sz, root[SIZE];
void upd(int &pos, int l, int r, int p) {
    node[++sz] = node[pos];
    pos = sz;
    node[pos].cnt++;
    node[pos].sum += a[p].F;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (p <= mid) upd(node[pos].ls, l, mid, p);
    else upd(node[pos].rs, mid + 1, r, p);
}
Node que(int tl, int tr, int l, int r, int L, int R) {
    if (l == L && r == R) return node[tr] - node[tl];
    int mid = (L + R) / 2;
    Node &nl = node[tl], &nr = node[tr];
    if (r <= mid) return que(nl.ls, nr.ls, l, r, L, mid);
    if (l > mid) return que(nl.rs, nr.rs, l, r, mid + 1, R);
    return que(nl.ls, nr.ls, l, mid, L, mid) + que(nl.rs, nr.rs, mid + 1, r, mid + 1, R);
}

int w[SIZE], son[SIZE], dep[SIZE], pa[SIZE], top[SIZE];
void dfs1(int pos) {
    w[pos] = 1;
    for (int np : adj[pos]) if (np != pa[pos]) {
        dep[np] = dep[pos] + 1;
        pa[np] = pos;
        dfs1(np);
        w[pos] += w[np];
        if (w[np] > w[son[pos]]) son[pos] = np;
    }
}
void dfs2(int pos) {
    if (top[pos] != 0) root[pos] = root[pa[pos]];
    else top[pos] = pos;
    for (int i : op[pos]) upd(root[pos], 1, m, i);
    if (son[pos]) {
        top[son[pos]] = top[pos];
        dfs2(son[pos]);
    }
    for (int np : adj[pos]) if (np != pa[pos] && np != son[pos]) {
        dfs2(np);
    }
}

int que_cnt(int a, int b) {
    int cnt = 0;
    while (true) {
        if (top[a] == top[b]) {
            if (dep[a] > dep[b]) swap(a, b);
            int tl = (a == top[a] ? 0 : root[pa[a]]), tr = root[b];
            cnt += node[tr].cnt - node[tl].cnt;
            break;
        }
        if (dep[top[a]] < dep[top[b]]) swap(a, b);
        cnt += node[root[a]].cnt;
        a = pa[top[a]];
    }
    return cnt;
}
int cal(int r, int a, int b, ll lim) {
    if (r == 0) return 0;
    int cnt = 0;
    ll sum = 0;
    while (sum <= lim) {
        if (top[a] == top[b]) {
            if (dep[a] > dep[b]) swap(a, b);
            int tl = (a == top[a] ? 0 : root[pa[a]]), tr = root[b];
            Node nd = que(tl, tr, 1, r, 1, m);
            cnt += nd.cnt, sum += nd.sum;
            break;
        }
        if (dep[top[a]] < dep[top[b]]) swap(a, b);
        Node nd = que(0, root[a], 1, r, 1, m);
        cnt += nd.cnt, sum += nd.sum;
        a = pa[top[a]];
    }
    if (sum > lim) return -1;
    return cnt;
}

void solve() {
    cin >> n >> m >> q;
    FOR (i, 1, n - 1) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(n + i), adj[n + i].pb(a);
        adj[b].pb(n + i), adj[n + i].pb(b);
    }
    FOR (i, 1, m) {
        auto &[val, p] = a[i];
        cin >> p >> val;
        p += n;
    }
    sort(a + 1, a + m + 1);
    FOR (i, 1, m) op[a[i].S].pb(i);
    dep[1] = 1, dfs1(1), dfs2(1);
    while (q--) {
        int a, b, x;
        ll y;
        cin >> a >> b >> x >> y;
        int l = 0, r = m, k = que_cnt(a, b);
        while (l < r) {
            int mid = (l + r) / 2 + 1;
            if (cal(mid, a, b, y) >= 0) l = mid;
            else r = mid - 1;
        }
        int d = cal(l, a, b, y);
        if (x < k - d) cout << "-1\n";
        else cout << x - (k - d) << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

Compilation message (stderr)

currencies.cpp: In constructor 'Node::Node(int, long long int)':
currencies.cpp:31:8: warning: 'Node::sum' will be initialized after [-Wreorder]
   31 |     ll sum;
      |        ^~~
currencies.cpp:30:14: warning:   'int Node::ls' [-Wreorder]
   30 |     int cnt, ls, rs;
      |              ^~
currencies.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     Node(int cnt, ll sum) : cnt(cnt), sum(sum), ls(0), rs(0) {}
      |     ^~~~

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