Submission #1247361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247361		cbd_6969	Two Currencies (JOI23_currencies)	C++20	0 / 100	4 ms	7492 KiB

currencies

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

const int MAXN = 100000;
const int MAXQ = 100000;
const int LG = 17; // ~log2(100k)
// PST node count upper bound: (N + M) * log M
static int N, M, Q;
vector<pair<int,int>> tree_adj[MAXN+1]; // (neighbor, edge_id)
vector<ll> edge_costs[MAXN+1]; // unused
vector<ll> checkpoint_costs[MAXN];
int up[MAXN+1][LG], tin[MAXN+1], tout[MAXN+1], timer=0;
int edge_to_parent[MAXN+1];

// Compress silver costs
vector<ll> comp;
int SZ;

struct Node {
    int cnt;
    ll sum;
    int l, r;
} ;

// Maximum PST nodes ~ (N + total_checkpoints) * log
static Node seg[40 * (MAXN + MAXQ)];
static int root[MAXN+1];
static int nxt = 0;

int new_node(int cnt=0, ll sum=0, int l=0, int r=0) {
    int id = ++nxt;
    seg[id].cnt = cnt;
    seg[id].sum = sum;
    seg[id].l = l;
    seg[id].r = r;
    return id;
}

int build_empty(int tl, int tr) {
    int v = new_node(0,0,0,0);
    if (tl == tr) return v;
    int tm = (tl+tr)/2;
    seg[v].l = build_empty(tl, tm);
    seg[v].r = build_empty(tm+1, tr);
    return v;
}

int update(int prev, int tl, int tr, int pos, ll cost) {
    int v = new_node();
    if (tl == tr) {
        seg[v].cnt = seg[prev].cnt + 1;
        seg[v].sum = seg[prev].sum + cost;
        return v;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) {
        seg[v].l = update(seg[prev].l, tl, tm, pos, cost);
        seg[v].r = seg[prev].r;
    } else {
        seg[v].l = seg[prev].l;
        seg[v].r = update(seg[prev].r, tm+1, tr, pos, cost);
    }
    seg[v].cnt = seg[seg[v].l].cnt + seg[seg[v].r].cnt;
    seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
    return v;
}

void dfs_lca(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i < LG; i++) up[u][i] = up[ up[u][i-1] ][i-1];
    for (auto &ed : tree_adj[u]) {
        int v = ed.first;
        int eid = ed.second;
        if (v == p) continue;
        edge_to_parent[v] = eid;
        dfs_lca(v, u);
    }
    tout[u] = timer;
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (is_anc(u,v)) return u;
    if (is_anc(v,u)) return v;
    for (int i = LG-1; i >= 0; i--) {
        int w = up[u][i];
        if (w && !is_anc(w, v)) u = w;
    }
    return up[u][0];
}

void dfs_build(int u, int p) {
    // start from parent's version
    root[u] = root[p];
    // apply all checkpoint costs on edge (p,u)
    int eid = edge_to_parent[u];
    for (ll c : checkpoint_costs[eid]) {
        int pos = int(lower_bound(comp.begin(), comp.end(), c) - comp.begin()) + 1;
        root[u] = update(root[u], 1, SZ, pos, c);
    }
    for (auto &ed : tree_adj[u]) {
        int v = ed.first;
        if (v == p) continue;
        dfs_build(v, u);
    }
}

// find how many you can pay in silver within budget Y
int count_silver(int ru, int rv, int rp, int rpw, ll Y) {
    int paid = 0;
    int tl = 1, tr = SZ;
    int u1=ru, u2=rv, u3=rp, u4=rpw;
    ll rem = Y;
    while (tl < tr) {
        int tm = (tl+tr)/2;
        ll sumL = seg[seg[u1].l].sum + seg[seg[u2].l].sum
                 - seg[seg[u3].l].sum - seg[seg[u4].l].sum;
        int cntL = seg[seg[u1].l].cnt + seg[seg[u2].l].cnt
                 - seg[seg[u3].l].cnt - seg[seg[u4].l].cnt;
        if (sumL <= rem) {
            rem -= sumL;
            paid += cntL;
            // go right
            u1 = seg[u1].r;
            u2 = seg[u2].r;
            u3 = seg[u3].r;
            u4 = seg[u4].r;
            tl = tm+1;
        } else {
            // go left
            u1 = seg[u1].l;
            u2 = seg[u2].l;
            u3 = seg[u3].l;
            u4 = seg[u4].l;
            tr = tm;
        }
    }
    // at leaf tl==tr
    ll cost = comp[tl-1];
    int cntAll = seg[u1].cnt + seg[u2].cnt - seg[u3].cnt - seg[u4].cnt;
    // can pay extra = min(cntAll, rem / cost)
    ll extra = min<ll>(cntAll, rem / cost);
    paid += int(extra);
    return paid;
}

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

    cin >> N >> M >> Q;
    // read tree edges
    for (int i = 1; i < N; i++) {
        int u,v; cin>>u>>v;
        tree_adj[u].push_back({v,i});
        tree_adj[v].push_back({u,i});
    }
    // read checkpoints
    for (int i = 1; i <= M; i++) {
        int a,b; ll c; 
        cin>>a>>b>>c;
        // checkpoint on edge (a,b)
        // find edge id: because it's tree, either adj[a] has (b,i) or vice versa
        // We'll store on both directions: use a map for speed
        checkpoint_costs[i].push_back(c);
        comp.push_back(c);
    }
    // compress
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    SZ = comp.size();

    // LCA prep
    dfs_lca(1, 0);
    // build PST
    root[0] = build_empty(1, SZ);
    dfs_build(1, 0);

    while (Q--) {
        int s,t; ll X_silver, Y_gold;
        cin>>s>>t>>X_silver>>Y_gold;
        int p = lca(s,t);
        int pw = up[p][0];
        // total checkpoints on path K
        int totalCnt = seg[root[s]].cnt + seg[root[t]].cnt
                     - seg[root[p]].cnt - seg[root[pw]].cnt;
        int paid = count_silver(root[s], root[t], root[p], root[pw], Y_gold);
        int goldNeeded = totalCnt - paid;
        if (goldNeeded > X_silver) cout<<-1<<"\n";
        else cout<< (X_silver - goldNeeded) <<"\n";
    }
    return 0;
}

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