제출 #1217428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217428		BuiDucManh123	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	5956 KiB

currencies

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

const int MAXN = 200000;

int N, M, Q;
vector<pair<int,int>> adj[MAXN+1];
int U[MAXN+1], V[MAXN+1];

int parent_[MAXN+1], depth[MAXN+1], heavy[MAXN+1], sz[MAXN+1];
int head[MAXN+1], pos[MAXN+1], curPos;
int edgeIdAtNode[MAXN+1];

vector<ll> allC;
int rootAtNode[MAXN+1];

struct Node {
    int l, r;
    int cnt;
    ll sum;
} seg[MAXN * 40];
int segCnt = 0;

int build(int nl,int nr){
    int id = ++segCnt;
    seg[id].l = seg[id].r = 0;
    seg[id].cnt = seg[id].sum = 0;
    if(nl < nr){
        int m = (nl+nr)>>1;
        seg[id].l = build(nl,m);
        seg[id].r = build(m+1,nr);
    }
    return id;
}

int update(int old,int nl,int nr,int pos){
    int id = ++segCnt;
    seg[id] = seg[old];
    if(nl==nr){
        seg[id].cnt += 1;
        seg[id].sum += allC[nl-1];
    } else {
        int m=(nl+nr)>>1;
        if(pos<=m) seg[id].l = update(seg[old].l, nl,m,pos);
        else       seg[id].r = update(seg[old].r, m+1,nr,pos);
        seg[id].cnt = seg[ seg[id].l ].cnt + seg[ seg[id].r ].cnt;
        seg[id].sum = seg[ seg[id].l ].sum + seg[ seg[id].r ].sum;
    }
    return id;
}

ll query_kth_sum(int a,int b,int c,int d,int nl,int nr,int k){
    if(k<=0) return 0;
    if(nl==nr){
        return allC[nl-1] * 1LL * k;
    }
    int cntL = seg[ seg[a].l ].cnt
             + seg[ seg[b].l ].cnt
             - seg[ seg[c].l ].cnt
             - seg[ seg[d].l ].cnt;
    int m=(nl+nr)>>1;
    if(k <= cntL){
        return query_kth_sum(seg[a].l, seg[b].l, seg[c].l, seg[d].l,
                             nl, m, k);
    } else {
        ll sumL = seg[ seg[a].l ].sum
                + seg[ seg[b].l ].sum
                - seg[ seg[c].l ].sum
                - seg[ seg[d].l ].sum;
        return sumL
             + query_kth_sum(seg[a].r, seg[b].r, seg[c].r, seg[d].r,
                             m+1, nr, k - cntL);
    }
}

vector<vector<int>> atChecksOnEdge;

int dfs1(int u,int p){
    parent_[u]=p;
    depth[u]=(p==0?0:depth[p]+1);
    sz[u]=1; heavy[u]=0;
    for(auto &e:adj[u]){
        int v=e.first, ei=e.second;
        if(v==p) continue;
        edgeIdAtNode[v]=ei;
        int s = dfs1(v,u);
        sz[u]+=s;
        if(s > sz[ heavy[u] ]) heavy[u]=v;
    }
    return sz[u];
}

void dfs2(int u,int h){
    head[u]=h;
    pos[u]=++curPos;
    rootAtNode[u] = (u==1? rootAtNode[1] : rootAtNode[parent_[u]]);
    for(int cc: atChecksOnEdge[ edgeIdAtNode[u] ]) {
        rootAtNode[u] = update(rootAtNode[u], 1, M, cc);
    }
    if(heavy[u]) dfs2(heavy[u], h);
    for(auto &e:adj[u]){
        int v=e.first;
        if(v==parent_[u] || v==heavy[u]) continue;
        dfs2(v, v);
    }
}

int lca(int a,int b){
    while(head[a]!=head[b]){
        if(depth[ head[a] ] > depth[ head[b] ])
            a = parent_[ head[a] ];
        else
            b = parent_[ head[b] ];
    }
    return depth[a]<depth[b]? a:b;
}

void path_roots(int u,int v, int &ru, int &rv, int &rlca, int &rplca){
    int w = lca(u,v);
    ru   = rootAtNode[u];
    rv   = rootAtNode[v];
    rlca = rootAtNode[w];
    int pw = parent_[w];
    rplca = (pw==0? 0 : rootAtNode[pw]);
}

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

    cin >> N >> M >> Q;
    for(int i=1;i<N;i++){
        cin >> U[i] >> V[i];
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }

    vector<pair<int,ll>> checks(M);
    for(int i=0;i<M;i++){
        cin >> checks[i].first >> checks[i].second;
        allC.push_back(checks[i].second);
    }

    sort(allC.begin(), allC.end());
    allC.erase(unique(allC.begin(), allC.end()), allC.end());

    atChecksOnEdge.assign(N+1, {});
    for(auto &p:checks){
        int eidx = p.first;
        ll c    = p.second;
        int cc   = int(lower_bound(allC.begin(), allC.end(), c) - allC.begin()) + 1;
        atChecksOnEdge[eidx].push_back(cc);
    }

    dfs1(1,0);
    rootAtNode[1] = build(1, M);
    dfs2(1,1);

    while(Q--){
        int s,t;
        ll X,Y;
        cin >> s >> t >> X >> Y;
        int ru,rv,rlca,rplca;
        path_roots(s,t, ru,rv,rlca,rplca);
        int totCnt = seg[ru].cnt + seg[rv].cnt - seg[rlca].cnt - seg[rplca].cnt;
        int lo=0, hi=totCnt, best=0;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            ll sumK = query_kth_sum(ru,rv,rlca,rplca, 1,M, mid);
            if(sumK <= Y){
                best = mid;
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        int silverPaid = best;
        int goldNeeded = totCnt - silverPaid;
        if(goldNeeded > X) cout << -1 << "\n";
        else               cout << (X - goldNeeded) << "\n";
    }
    return 0;
}

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