Submission #946008

#	Time	Username	Problem	Language	Result	Execution time	Memory
946008		peteza	Two Currencies (JOI23_currencies)	C++14	100 / 100	664 ms	124904 KiB

currencies

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

struct node {
    node *l = NULL, *r = NULL;
    int sz = 0;
    ll sum = 0;
} *root[100005];

int n, m, q;
ll a, b, c, d;
pair<int, int> edges[100005];
vector<int> prices[100005];
vector<int> adj[100005];
int par[100005][22], dep[100005];

node* build(int l, int r) {
    auto it = new node();
    if(l == r) return it;
    int mid = (l+r) >> 1;
    it->l = build(l, mid); it->r = build(mid+1, r);
    return it;
}

node *upd(node*&old, int l, int r, int tgt, int val) {
    auto it = new node();
    if(l == r) {it->sz=1; it->sum = val; return it;}
    int mid = (l+r) >> 1;
    if(tgt <= mid) it->l = upd(old->l, l, mid, tgt, val), it->r = old->r;
    else          it->r = upd(old->r, mid+1, r, tgt,val), it->l = old->l;
    it->sz  = it->l->sz  + it->r->sz ;
    it->sum = it->l->sum + it->r->sum;
    return it;
}

void dfsdep(int x, int p = 0) {
    dep[x] = dep[p] + 1;
    par[x][0] = p;
    for(int i=1;i<20;i++) par[x][i] = par[par[x][i-1]][i-1];
    for(int e:adj[x]) {
        if(e != p) dfsdep(e, x);
    }
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) swap(a, b);
    for(int i=19;i>=0;i--) if(dep[a] <= dep[par[b][i]]) b = par[b][i];
    if(a == b) return a;
    for(int i=19;i>=0;i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
    return par[a][0];
}

int pos[100005];
vector<pair<int, int>> edgesprices;

void dfspart2(int x, int p = 0) {
    root[x] = root[p];
    for(auto e:prices[x]) {
        root[x] = upd(root[x], 1, m, pos[e], edgesprices[pos[e]-1].first);    
    }
    //cout << x << ": " << root[x]->sz << "-> " << root[x]->sum << '\n';
    for(int e:adj[x]) {
        if(e != p)
            dfspart2(e, x);
    }
}

int qr(node *& ra, node*& rb, node*& lca, int l, int r, ll tgt) {
    if(l == r) return ((ra->sz + rb->sz - lca->sz*2) && (tgt >= ra->sum + rb->sum - lca->sum*2));
    if(!ra) return 0;
    int mid = (l+r) >> 1;
    ll silleft = ra->l->sum + rb->l->sum - lca->l->sum*2;
    if(silleft <= tgt) return ra->l->sz + rb->l->sz - lca->l->sz*2 + qr(ra->r, rb->r, lca->r, mid+1, r, tgt-silleft);
    else return qr(ra->l, rb->l, lca->l, l, mid, tgt);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=1;i<n;i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges[i] = {a, b};
    }
    root[0] = build(1, m);
    dfsdep(1);
    for(int i=1;i<=m;i++) {
        cin >> a >> b;
        if(dep[edges[a].first] > dep[edges[a].second]) swap(edges[a].first, edges[a].second);
        prices[edges[a].second].emplace_back(i);
        edgesprices.emplace_back(b, i);
    }
    sort(edgesprices.begin(), edgesprices.end());
    for(int i=0;i<m;i++) pos[edgesprices[i].second] = i+1;
    dfspart2(1);
    while(q--) {
        cin >> a >> b >> c >> d;
        int lcab = lca(a, b);
        ll silvercnt = root[a]->sz + root[b]->sz - 2*root[lcab]->sz;
        cout << max(-1ll, c-(silvercnt-qr(root[a], root[b], root[lcab], 1, m, d))) << '\n';
    }
}

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