Submission #979015

#	Time	Username	Problem	Language	Result	Execution time	Memory
979015		abc864197532	Two Currencies (JOI23_currencies)	C++17	100 / 100	510 ms	129192 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int N = 100087, mod = 998244353, M = N * 40, logN = 19;

vector <int> vec;

struct Seg {
    static Seg mem[M], *pt;
    int l, r, m, cnt;
    ll sum;
    Seg* ch[2];
    Seg () = default;
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), sum(0), cnt(0) {
        if (r - l > 1) {
            ch[0] = new (pt++) Seg(l, m);
            ch[1] = new (pt++) Seg(m, r);
        }
    }
    Seg (Seg *i) : l(i->l), r(i->r), m(i->m), sum(i->sum), cnt(i->cnt), ch{i->ch[0], i->ch[1]} {}
    void pull() {sum = ch[0]->sum + ch[1]->sum, cnt = ch[0]->cnt + ch[1]->cnt;}
    Seg* modify(int p) {
        Seg *now = new (pt++) Seg(*this);
        if (r - l == 1) {
            now->sum += vec[l];
            now->cnt += 1;
        } else {
            now->ch[p >= m] = ch[p >= m]->modify(p);
            now->pull();
        }
        return now;
    }
} Seg::mem[M], *Seg::pt = mem;


vector <pii> adj[N];
vector <int> cost[N];
int jump[N][logN], in[N], out[N], _t;
Seg* val[N];

void dfs(int v, int pa) {
    in[v] = _t++, jump[v][0] = pa;
    for (int j = 1; j < logN; ++j) {
        int k = jump[v][j - 1];
        jump[v][j] = ~k ? jump[k][j - 1] : -1;
    }
    for (auto [u, eid] : adj[v]) if (u != pa) {
        val[u] = new (Seg::pt++) Seg(val[v]);
        for (int w : cost[eid]) {
            int id = lower_bound(all(vec), w) - vec.begin();
            val[u] = val[u]->modify(id);
        }
        dfs(u, v);
    }
    out[v] = _t++;
}

int anc(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v) {
    if (anc(u, v)) {
        return u;
    }
    if (anc(v, u)) {
        return v;
    }
    for (int i = logN - 1; ~i; --i) {
        if (~jump[u][i] && !anc(jump[u][i], v)) {
            u = jump[u][i];
        }
    }
    return jump[u][0];
}

int query(int u, int v, ll tot) {
    int l = lca(u, v);
    Seg *tl = val[u], *tr = val[v], *tm = val[l];
    int ans = 0;
    while (tl->r - tl->l > 1) {
        ll left = tl->ch[0]->sum + tr->ch[0]->sum - 2 * tm->ch[0]->sum;
        if (left <= tot) {
            tl = tl->ch[1];
            tr = tr->ch[1];
            tm = tm->ch[1];
            tot -= left;
        } else {
            ans += tl->ch[1]->cnt + tr->ch[1]->cnt - 2 * tm->ch[1]->cnt;
            tl = tl->ch[0];
            tr = tr->ch[0];
            tm = tm->ch[0];
        }
    }
    int tmp = tl->cnt + tr->cnt - 2 * tm->cnt;
    ans += tmp - min(tot / vec[tl->l], 1ll * tmp);
    return ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v, --u;
        cost[u].pb(v);
        vec.pb(v);
    }
    sort(all(vec)), vec.resize(unique(all(vec)) - vec.begin());
    val[0] = new (Seg::pt++) Seg(0, int(vec.size()));
    dfs(0, -1);
    while (q--) {
        int u, v, x; ll y;
        cin >> u >> v >> x >> y, --u, --v;
        int tmp = query(u, v, y);
        cout << max(x - tmp, -1) << '\n';
    }
}

/*
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
*/

Compilation message (stderr)

currencies.cpp: In constructor 'Seg::Seg(int, int)':
currencies.cpp:17:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), sum(0), cnt(0) {
      |                                            ~~^~~
currencies.cpp:14:8: warning: 'Seg::sum' will be initialized after [-Wreorder]
   14 |     ll sum;
      |        ^~~
currencies.cpp:13:18: warning:   'int Seg::cnt' [-Wreorder]
   13 |     int l, r, m, cnt;
      |                  ^~~
currencies.cpp:17:5: warning:   when initialized here [-Wreorder]
   17 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), sum(0), cnt(0) {
      |     ^~~
currencies.cpp: In constructor 'Seg::Seg(Seg*)':
currencies.cpp:14:8: warning: 'Seg::sum' will be initialized after [-Wreorder]
   14 |     ll sum;
      |        ^~~
currencies.cpp:13:18: warning:   'int Seg::cnt' [-Wreorder]
   13 |     int l, r, m, cnt;
      |                  ^~~
currencies.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     Seg (Seg *i) : l(i->l), r(i->r), m(i->m), sum(i->sum), cnt(i->cnt), ch{i->ch[0], i->ch[1]} {}
      |     ^~~

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