Submission #874565

#	Time	Username	Problem	Language	Result	Execution time	Memory
874565		onlk97	Two Currencies (JOI23_currencies)	C++14	100 / 100	2984 ms	67588 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
int n,m,q;
vector <int> g[100010];
pair <int,int> edg[100010],op[100010];
int dep[100010],pa[100010][17],siz[100010],hson[100010];
void dfs1(int cur,int prv){
    if (prv) dep[cur]=dep[prv]+1;
    pa[cur][0]=prv;
    siz[cur]=1;
    int mxz=0;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs1(i,cur);
        siz[cur]+=siz[i];
        if (siz[i]>mxz){
            mxz=siz[i];
            hson[cur]=i;
        }
    }
}
int curidx,id[100010],tp[100010];
void dfs2(int cur,int topn){
    id[cur]=++curidx;
    tp[cur]=topn;
    if (!hson[cur]) return;
    dfs2(hson[cur],topn);
    for (int i:g[cur]){
        if (i!=pa[cur][0]&&i!=hson[cur]) dfs2(i,i);
    }
}
pair <long long,int> seg[400040];
void update(int id,int tl,int tr,int pos,long long val){
    if (tl==tr){
        seg[id].first+=val;
        if (val>0) seg[id].second++;
        else seg[id].second--; 
        return;
    }
    int tm=(tl+tr)/2;
    if (pos<=tm) update(2*id,tl,tm,pos,val);
    else update(2*id+1,tm+1,tr,pos,val);
    seg[id].first=seg[2*id].first+seg[2*id+1].first;
    seg[id].second=seg[2*id].second+seg[2*id+1].second;
}
pair <long long,int> Query(int id,int tl,int tr,int l,int r){
    if (l>r) return {0LL,0};
    if (l<=tl&&tr<=r) return seg[id];
    int tm=(tl+tr)/2;
    pair <long long,int> lx=Query(2*id,tl,tm,l,min(r,tm));
    pair <long long,int> rx=Query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return {lx.first+rx.first,lx.second+rx.second};
}
pair <long long,int> query(int u,int v){
    pair <long long,int> ans={0,0};
    while (tp[u]!=tp[v]){
        if (dep[tp[u]]<dep[tp[v]]) swap(u,v);
        pair <long long,int> tt=Query(1,1,n,id[tp[u]],id[u]);
        ans.first+=tt.first; ans.second+=tt.second;
        u=pa[tp[u]][0];
    }
    if (dep[u]>dep[v]) swap(u,v);
    pair <long long,int> tt=Query(1,1,n,id[u],id[v]);
    ans.first+=tt.first; ans.second+=tt.second;
    tt=Query(1,1,n,id[u],id[u]);
    return {ans.first-tt.first,ans.second-tt.second};
}
int cnt[100010],ccnt[100010];
void solve(int ansl,int ansr,vector <pair <pair <int,int>,pair <long long,int> > > v){
    if (ansl==ansr||v.empty()){
        for (auto i:v) ccnt[i.second.second]=query(i.first.first,i.first.second).second;
        return;
    }
    int mid=(ansl+ansr)/2;
    for (int i=ansl; i<=mid; i++) update(1,1,n,id[op[i].second],op[i].first);
    vector <pair <pair <int,int>,pair <long long,int> > > vl,vr;
    for (auto i:v){
        if (query(i.first.first,i.first.second).first>i.second.first) vl.push_back(i);
        else vr.push_back(i);
    }
    solve(mid+1,ansr,vr);
    for (int i=ansl; i<=mid; i++) update(1,1,n,id[op[i].second],-op[i].first);
    solve(ansl,mid,vl);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++){
        cin>>edg[i].first>>edg[i].second;
        g[edg[i].first].push_back(edg[i].second);
        g[edg[i].second].push_back(edg[i].first);
    }
    dfs1(1,0);
    for (int j=1; j<17; j++){
        for (int i=1; i<=n; i++) pa[i][j]=pa[pa[i][j-1]][j-1];
    }
    dfs2(1,1);
    for (int i=1; i<=m; i++){
        int u;
        cin>>u>>op[i].first;
        if (dep[edg[u].first]>dep[edg[u].second]) op[i].second=edg[u].first;
        else op[i].second=edg[u].second;
    }
    sort(op+1,op+m+1);
    pair <pair <int,int>,pair <long long,int> > qu[q+1];
    for (int i=1; i<=q; i++) cin>>qu[i].first.first>>qu[i].first.second>>qu[i].second.second>>qu[i].second.first;
    for (int i=1; i<=m; i++) update(1,1,n,id[op[i].second],1);
    for (int i=1; i<=q; i++) cnt[i]=query(qu[i].first.first,qu[i].first.second).first;
    for (int i=1; i<=m; i++) update(1,1,n,id[op[i].second],-1);
    vector <pair <pair <int,int>,pair <long long,int> > > v;
    for (int i=1; i<=q; i++) v.push_back({qu[i].first,{qu[i].second.first,i}});
    solve(1,m+1,v);
    for (int i=1; i<=q; i++){
        int lef=cnt[i]-ccnt[i];
        if (lef>qu[i].second.second) cout<<"-1\n";
        else cout<<qu[i].second.second-lef<<'\n';
    }
}

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