Submission #1223040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223040		minhpk	Two Currencies (JOI23_currencies)	C++20	28 / 100	2343 ms	134064 KiB

currencies

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

static const int MAXA = 1000000;
int a, b, c;
vector<int> z[MAXA+5];
pair<int,int> t[MAXA+5], edge[MAXA+5];
int logarit[2*MAXA+5];
int sta[MAXA*2+5], fin[MAXA*2+5], euler[MAXA*2+5], tour=0;
int st[MAXA*2+5][22], high[MAXA+5];
int sta1[MAXA+5], fin1[MAXA+5], tour1=0;

struct SegmentTree {
    int tree[4*MAXA*2+5], lazy[4*MAXA*2+5];
    void build(int id,int l,int r){
        tree[id]=lazy[id]=0;
        if(l==r) return;
        int m=(l+r)>>1;
        build(id<<1,l,m);
        build(id<<1|1,m+1,r);
    }
    void push(int id){
        if(lazy[id]){
            int v=lazy[id];
            tree[id<<1]+=v; lazy[id<<1]+=v;
            tree[id<<1|1]+=v; lazy[id<<1|1]+=v;
            lazy[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){
            tree[id]+=v; lazy[id]+=v;
            return;
        }
        push(id);
        int m=(l+r)>>1;
        update(id<<1,l,m,ql,qr,v);
        update(id<<1|1,m+1,r,ql,qr,v);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    int get(int id,int l,int r,int pos){
        if(l==r) return tree[id];
        push(id);
        int m=(l+r)>>1;
        return pos<=m
            ? get(id<<1,l,m,pos)
            : get(id<<1|1,m+1,r,pos);
    }
} f, f1;

struct Query { int x,y,g,val; };
Query q[MAXA+5];
vector<int> v[MAXA+5];
int L[MAXA+5], R[MAXA+5], ans1[MAXA+5], ans2[MAXA+5];

void dfs(int u,int p){
    sta[u]=++tour; euler[tour]=u;
    tour1++;
     sta1[u]=tour1;
    for(int w:z[u]) if(w!=p){
        high[w]=high[u]+1;
        dfs(w,u);
        euler[++tour]=u;
    }
    fin[u]=tour;
    fin1[u]=tour1;
}

void buildst(){
    for(int i=1;i<=tour;i++) st[i][0]=euler[i];
    for(int j=1;j<=logarit[tour];j++){
        for(int i=1;i+(1<<j)-1<=tour;i++){
            int x=st[i][j-1], y=st[i+(1<<(j-1))][j-1];
            st[i][j]= (high[x]<high[y]?x:y);
        }
    }
}

int lca(int x,int y){
    int L=min(sta[x],sta[y]), R=max(sta[x],sta[y]);
    int k=logarit[R-L+1];
    int u=st[L][k], v=st[R-(1<<k)+1][k];
    return high[u]<high[v]?u:v;
}

int calc(int u,int v){
    int su=f.get(1,1,tour1,sta1[u]);
    int sv=f.get(1,1,tour1,sta1[v]);
    int sl=f.get(1,1,tour1,sta1[lca(u,v)]);
    return su+sv-2*sl;
}
int calc1(int u,int v){
    int su=f1.get(1,1,tour1,sta1[u]);
    int sv=f1.get(1,1,tour1,sta1[v]);
    int sl=f1.get(1,1,tour1,sta1[lca(u,v)]);
    return su+sv-2*sl;
}

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

    cin>>a>>b>>c;
    for(int i=1;i<a;i++){
        int x,y; cin>>x>>y;
        z[x].push_back(y);
        z[y].push_back(x);
        edge[i]={x,y};
    }
    for(int i=1;i<=b;i++) cin>>t[i].first>>t[i].second;

    logarit[1]=0;
    for(int i=2;i<=2*a;i++) logarit[i]=logarit[i>>1]+1;

    dfs(1,0);
    buildst();

    for(int i=1;i<=c;i++){
        cin>>q[i].x>>q[i].y>>q[i].g>>q[i].val;
        L[i]=1; R[i]=b; ans1[i]=ans2[i]=0;
    }

    while(true){
        // ←—— clear all buckets BEFORE assigning mids
        for(int i=1;i<=b;i++) v[i].clear();

        bool any=false;
        for(int i=1;i<=c;i++){
            if(L[i]<=R[i]){
                any=true;
                int mid=(L[i]+R[i])>>1;
                v[mid].push_back(i);
            }
        }
        if(!any) break;

        f.build(1,1,tour1);
        f1.build(1,1,tour1);

        for(int i=1;i<=b;i++){
            auto [X,W] = t[i];
            int u=edge[X].first, v1=edge[X].second;
            if(high[u]<high[v1]) swap(u,v1);
            f.update(1,1,tour1,sta1[u],fin1[u],W);
            f1.update(1,1,tour1,sta1[u],fin1[u],1);

            for(int qi:v[i]){
                int got=calc(q[qi].x,q[qi].y);
                if(got<=q[qi].val){
                    ans1[qi]=i;
                    ans2[qi]=calc1(q[qi].x,q[qi].y);
                    L[qi]=i+1;
                } else {
                    R[qi]=i-1;
                }
            }
        }
    }
    f1.build(1,1,tour1);
    for (int i=1;i<=b;i++){
        auto [X,W] = t[i];
        int u=edge[X].first, v1=edge[X].second;
        if(high[u]<high[v1]) swap(u,v1);
        f1.update(1,1,tour1,sta1[u],fin1[u],1);
    }
    for(int i=1;i<=c;i++){

            int tot=calc1(q[i].x,q[i].y);
            int used=ans2[i];
            int over=tot-used;
          //  cout << tot << ' ';
           if (over>q[i].g){
                cout << -1 << '\n';
           }else{
               cout << q[i].g - over << '\n';
           }
        
    }
    return 0;
}

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