Submission #942465

#	Time	Username	Problem	Language	Result	Execution time	Memory
942465		tosivanmak	Two Currencies (JOI23_currencies)	C++17	100 / 100	2136 ms	172188 KiB

currencies

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

ll ver[100005],tin[100005],ass=0;
bool vis[100005];
vector<pair<ll,ll> >adj[100005];
ll uu[100005],v[100005],cnt[100005];
vector<ll>roads[100005];
vector<ll>disc;
ll revdisc[100005];
ll up[100005][20];
ll dep[100005];
ll assver=1;
ll siz;
struct EZOKUSEG{
    vector<vector<ll> >seg;
    vector<vector<ll> >chl,chr,cntt;
    void init(ll n){
        seg.resize(4*n+5),chl.resize(4*n+5),chr.resize(4*n+5),cntt.resize(4*n+5);
    }
    void build(ll l, ll r, ll id){
        seg[id].pb(0);
        chl[id].pb(0),chr[id].pb(0),cntt[id].pb(0);
        if(l==r){
            return;
        }
        ll mid=(l+r)>>1;
        build(l,mid,id*2);
        build(mid+1,r,id*2+1);
    }
    void upd(ll ver, ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[id].pb(seg[id][ver]+val);
            cntt[id].pb(cntt[id][ver]+1);
            return;
        }
        else{
            ll mid=(l+r)>>1;
            if(ul<=mid){
                upd(chl[id][ver],ul,l,mid,val,id*2);
                ll st=seg[id*2].size()-1,st2=chr[id][ver];
                chl[id].pb(seg[id*2].size()-1);
                chr[id].pb(chr[id][ver]);
                seg[id].pb(seg[id*2][st]+seg[id*2+1][st2]);
                cntt[id].pb(cntt[id*2][st]+cntt[id*2+1][st2]);
            }
            else{
                upd(chr[id][ver],ul,mid+1,r,val,id*2+1);
                ll st=chl[id][ver],st2=seg[id*2+1].size()-1;
                chl[id].pb(st);
                chr[id].pb(st2);
                seg[id].pb(seg[id*2][st]+seg[id*2+1][st2]);
                cntt[id].pb(cntt[id*2][st]+cntt[id*2+1][st2]);
            }
        }
    }
    ll sum(ll ver, ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return 0;
        }
        if(l>=ql&&r<=qr){
            return seg[id][ver];
        }
        ll mid=(l+r)>>1;
        return sum(chl[id][ver],ql,qr,l,mid,id*2)+sum(chr[id][ver],ql,qr,mid+1,r,id*2+1);
    }
    ll sum2(ll ver, ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return 0;
        }
        if(l>=ql&&r<=qr){
            return cntt[id][ver];
        }
        ll mid=(l+r)>>1;
        return sum2(chl[id][ver],ql,qr,l,mid,id*2)+sum2(chr[id][ver],ql,qr,mid+1,r,id*2+1);
    }
}st;
void dfs(ll s, ll p, ll k){
    vis[s]=1;
    tin[s]=ass++;
    ll curver=ver[p];
    for(int i=0;i<roads[k].size();i++){
        ll popo=lower_bound(disc.begin(),disc.end(),roads[k][i])-disc.begin()+1;
        st.upd(curver,popo,1,siz,roads[k][i],1);
        curver=assver++;
    }
    ver[s]=curver;
    for(pair<ll,ll>& u: adj[s]){
        if(!vis[u.first]){
            up[u.first][0]=s;
            dep[u.first]=dep[s]+1;
            dfs(u.first,s,u.second);
        }
    }
}
ll jump(ll u, ll k){
    for(int i=19;i>=0;i--){
        if(k&(1<<i)){
            u=up[u][i];
        }
    }
    return u;
}
ll lca(ll u, ll v){
    if(dep[u]<dep[v]){
        swap(u,v);
    }
    u=jump(u,dep[u]-dep[v]);
    if(u==v){
        return u;
    }
    for(int i=19;i>=0;i--){
        if(up[u][i]!=up[v][i]){
            u=up[u][i],v=up[v][i];
        }
    }
    return up[u][0];
}

bool ck(ll a, ll b, ll com, ll par, ll gin){
    ll tot=st.sum(ver[a],1,par,1,siz,1)+st.sum(ver[b],1,par,1,siz,1)-2*st.sum(ver[com],1,par,1,siz,1);
    return (gin>=tot);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n-1;i++){
        cin>>uu[i]>>v[i];
        adj[uu[i]].pb({v[i],i});
        adj[v[i]].pb({uu[i],i});
    }
    for(int i=1;i<=m;i++){
        ll p,c;
        cin>>p>>c;
        disc.pb(c);
        roads[p].pb(c);
        cnt[p]++;
    }
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());
    siz=disc.size();
    st.init(disc.size());
    st.build(1,siz,1);
    for(int i=0;i<disc.size();i++){
        revdisc[i+1]=disc[i];
    }
    ver[0]=0;
    ver[1]=0;
    dfs(1,0,0);
    up[1][0]=1;
    for(int j=1;j<=19;j++){
        for(int i=1;i<=n;i++){
            up[i][j]=up[up[i][j-1]][j-1];
        }
    }
    // for(int i=1;i<=n;i++){
    //     cout<<ver[i]<<" ";
    // }
    // cout<<st.sum(ver[4],1,siz,1,siz,1)<<'\n';
    while(q--){
        ll s,t,kin,gin;
        cin>>s>>t>>kin>>gin;
        ll com=lca(s,t);
        ll l=1,r=disc.size();
        while(l<r){
            ll mid=(l+r)>>1;
            // cout<<mid<<'\n';
            if(ck(s,t,com,mid,gin)){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        if(ck(s,t,com,l,gin)){
            cout<<kin<<'\n';
            continue;
        }
        ll tot=st.sum(ver[s],1,l-1,1,siz,1)+st.sum(ver[t],1,l-1,1,siz,1)-2*st.sum(ver[com],1,l-1,1,siz,1);
        ll used=st.sum2(ver[s],1,l-1,1,siz,1)+st.sum2(ver[t],1,l-1,1,siz,1)-2*st.sum2(ver[com],1,l-1,1,siz,1);
        gin-=tot;
        ll ned=revdisc[l];
        gin/=ned;
        used+=gin;
        ll bruh=st.sum2(ver[s],1,siz,1,siz,1)+st.sum2(ver[t],1,siz,1,siz,1)-2*st.sum2(ver[com],1,siz,1,siz,1);
        bruh-=used;
        // cout<<bruh<<'\n';
        if(kin>=bruh){
            cout<<kin-bruh<<'\n';
        }
        else{
            cout<<"-1\n";
        }
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int, long long int)':
currencies.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<roads[k].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:148:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i=0;i<disc.size();i++){
      |                 ~^~~~~~~~~~~~

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