Submission #1223011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223011		minhpk	Two Currencies (JOI23_currencies)	C++20	0 / 100	25 ms	47428 KiB

currencies

#include <bits/stdc++.h>
#define int long long
using namespace std;

static const int MAXN = 1000000;
int N, M, Q;
vector<int> adj[MAXN+5];
pair<int,int> checkpoint[MAXN+5];
pair<int,int> edgeList[MAXN+5];

int log2table[2*MAXN+5];
int euler[2*MAXN+5], timer = 0;
int st[2*MAXN+5][22], depthArr[MAXN+5];
int firstPos[MAXN+5];

int tour1 = 0, in1[MAXN+5], out1[MAXN+5];

int LCA(int u, int v) {
    int l = firstPos[u], r = firstPos[v];
    if (l > r) swap(l, r);
    int k = log2table[r - l + 1];
    int a = st[l][k], b = st[r - (1<<k) + 1][k];
    return depthArr[a] < depthArr[b] ? a : b;
}

void dfs(int u, int p, int d) {
    depthArr[u] = d;
    firstPos[u] = ++timer;
    euler[timer] = u;
    for (int v: adj[u]) {
        if (v == p) continue;
        dfs(v, u, d+1);
        euler[++timer] = u;
    }
    in1[u] = ++tour1;
    out1[u] = tour1;
}

void buildLCA() {
    for (int i = 1; i <= timer; i++) {
        st[i][0] = euler[i];
    }
    int K = log2table[timer];
    for (int j = 1; j <= K; j++) {
        for (int i = 1; i + (1<<j) - 1 <= timer; i++) {
            int x = st[i][j-1], y = st[i + (1<<(j-1))][j-1];
            st[i][j] = depthArr[x] < depthArr[y] ? x : y;
        }
    }
}

struct SegTree {
    vector<int> t, lz;
    int n;
    void init(int _n) {
        n = _n;
        t.assign(4*n+4, 0);
        lz.assign(4*n+4, 0);
    }
    void apply(int id, int val) {
        t[id] += val;
        lz[id] += val;
    }
    void push(int id) {
        if (lz[id]) {
            apply(id<<1, lz[id]);
            apply(id<<1|1, lz[id]);
            lz[id] = 0;
        }
    }
    void update(int id, int l, int r, int ql, int qr, int v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(id, v);
            return;
        }
        int mid = (l+r)>>1;
        push(id);
        update(id<<1, l, mid, ql, qr, v);
        update(id<<1|1, mid+1, r, ql, qr, v);
        t[id] = t[id<<1] + t[id<<1|1];
    }
    int queryPoint(int id, int l, int r, int pos) {
        if (l == r) return t[id];
        int mid = (l+r)>>1;
        push(id);
        return pos <= mid
            ? queryPoint(id<<1, l, mid, pos)
            : queryPoint(id<<1|1, mid+1, r, pos);
    }
};

SegTree segW, segS;

struct Query {
    int u, v, G, Sneed;
};

Query Qs[MAXN+5];
int lo[MAXN+5], hi[MAXN+5], ansCp[MAXN+5], usedSilver[MAXN+5];
vector<int> bucket[MAXN+5];

int calcSilver(int u, int v) {
    int su = segW.queryPoint(1,1,tour1,in1[u]);
    int sv = segW.queryPoint(1,1,tour1,in1[v]);
    int sl = segW.queryPoint(1,1,tour1,in1[LCA(u,v)]);
    return su + sv - 2*sl;
}
int calcCount(int u, int v) {
    int su = segS.queryPoint(1,1,tour1,in1[u]);
    int sv = segS.queryPoint(1,1,tour1,in1[v]);
    int sl = segS.queryPoint(1,1,tour1,in1[LCA(u,v)]);
    return su + sv - 2*sl;
}

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

    cin >> N >> M >> Q;
    for(int i=1;i<N;i++){
        int A,B; cin>>A>>B;
        adj[A].push_back(B);
        adj[B].push_back(A);
        edgeList[i] = {A,B};
    }
    for(int i=1;i<=M;i++){
        cin>>checkpoint[i].first>>checkpoint[i].second;
    }
    log2table[1]=0;
    for(int i=2;i<=2*N;i++){
        log2table[i] = log2table[i>>1] + 1;
    }
    dfs(1,0,0);
    buildLCA();

    for(int i=1;i<=Q;i++){
        cin>>Qs[i].u>>Qs[i].v>>Qs[i].G>>Qs[i].Sneed;
        lo[i]=1; hi[i]=M; ansCp[i]=0; usedSilver[i]=0;
    }

    bool cont=true;
    while(cont){
        cont=false;
        for(int i=1;i<=M;i++) bucket[i].clear();
        for(int i=1;i<=Q;i++){
            if(lo[i]<=hi[i]){
                cont=true;
                bucket[(lo[i]+hi[i])>>1].push_back(i);
            }
        }
        if(!cont) break;

        segW.init(tour1);
        segS.init(tour1);

        for(int i=1;i<=M;i++){
            int ei = checkpoint[i].first;
            auto [u,v] = edgeList[ei];
            if(depthArr[u] < depthArr[v]) swap(u,v);
            segW.update(1,1,tour1, in1[u], out1[u], checkpoint[i].second);
            segS.update(1,1,tour1, in1[u], out1[u], 1);

            for(int qi: bucket[i]){
                int needS = calcSilver(Qs[qi].u, Qs[qi].v);
                if(needS <= Qs[qi].Sneed){
                    ansCp[qi] = i;
                    usedSilver[qi] = needS;
                    lo[qi] = i+1;
                } else {
                    hi[qi] = i-1;
                }
            }
        }
    }

    for(int i=1;i<=Q;i++){
        if(ansCp[i]==0){
            cout << -1 << "\n";
        } else {
            int silverUsed = usedSilver[i];
            int needGold = max(0LL, silverUsed - Qs[i].Sneed);
            cout << (Qs[i].G - needGold) << "\n";
        }
    }
    return 0;
}

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