Submission #1262003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262003		user736482	Two Currencies (JOI23_currencies)	C++20	100 / 100	3805 ms	58180 KiB

currencies

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007 
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
#define X 17
ll pre[100007],mxpre[100007];
ll ans[100007];
ll n,a,b,c,m,q;
ll ak=1;
ll par[100007][X];
vector<ll>g[100007];
vector<pair<ll,ll>>ch;
vector<pair<pair<ll,ll>,ll>>zap;
ll pocz[100007],kon[100007],ilekup[100007],ilezap[100007];
ll sg[POT][2];
ll ilez[100007],iles[100007],dpt[100007];
void add(ll v,ll pocz,ll kon,ll l,ll r,ll x){
    if(r<pocz || l>kon)return;
    if(pocz<=l && kon>=r){sg[v][0]+=x;sg[v][1]++;}
    else{
        add(v*2,pocz,kon,l,(l+r)/2,x);
        add(v*2+1,pocz,kon,(l+r)/2+1,r,x);
    }
}
pair<ll,ll> gt(ll x){
    x=pre[x];
    x+=(POT/2-1);
    pair<ll,ll>odp={0,0};
    while(x){
        odp.ff+=sg[x][0];
        odp.ss+=sg[x][1];
        x/=2;
    }
    return odp;
}
void dfs(ll v,ll pop,ll dp){
    if(pop!=v)
    dpt[v]+=dpt[pop];
    pre[v]=ak++;
    par[v][0]=pop;
    for(ll i : g[v]){
        if(i!=pop)dfs(i,v,dp+1);
    }
    mxpre[v]=ak-1;
}
void dfs2(ll v,ll pop){
    if(pop!=v)
    dpt[v]+=dpt[pop];

    for(ll i : g[v]){
        if(i!=pop)dfs2(i,v);
    }

}
bool bl(ll a,ll b){
    return pre[a]>=pre[b] && pre[a]<=mxpre[b];
}
ll lca(ll a,ll b){
    if(bl(a,b))return b;
    if(bl(b,a))return a;
    for(ll j=X-1;j>=0;j--){
        if(!bl(b,par[a][j]))a=par[a][j];
        if(!bl(a,par[b][j]))b=par[b][j];
    }
    return par[a][0];
}
pair<ll,ll>dod(pair<ll,ll>a,pair<ll,ll>b){
    return {a.ff+b.ff,a.ss+b.ss};
}
pair<ll,ll>ode(pair<ll,ll>a,pair<ll,ll>b){
    return {a.ff-b.ff,a.ss-b.ss};
}
int main(){
    cin>>n>>m>>q;
    vector<pair<ll,ll>>e;
    for(ll i=1;i<n;i++){
        cin>>a>>b;
        e.pb({a,b});
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1,1,0);
    for(ll i=0;i<m;i++){
        cin>>a>>b;
        a--;
        if(par[e[a].ff][0]==e[a].ss)
        ch.pb({b,e[a].ff});
        else ch.pb({b,e[a].ss});
        dpt[ch.back().ss]++;
        //cout<<ch.back().ff<<" "<<ch.back().ss<<"\n";
    }
    dfs2(1,1);
    //cout<<"xd"<<flush;
    sort(ch.begin(),ch.end());
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        cin>>ilez[i]>>iles[i];
        zap.pb({{a,b},i});
        pocz[i]=0;
        kon[i]=1e9;
    }
    
    for(ll j=1;j<X;j++){
        for(ll i=1;i<=n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }
    
    for(ll k=0;k<31;k++){
        vector<pair<ll,ll>>op;//kiedy,idx || kiedy,-koszt
        for(auto i : zap)op.pb({(pocz[i.ss]+kon[i.ss])/2,i.ss});
        for(auto i : ch){
            op.pb({i.ff,-i.ss});
        }
        sort(op.begin(),op.end());
        for(ll j=1;j<POT;j++)sg[j][0]=sg[j][1]=0;
        for(auto i : op){
            
            //cout<<i.ff<<" "<<i.ss<<endl;
            if(i.ss<0){
                i.ss*=-1;
                //cout<<pre[i.ss]<<" "<<mxpre[i.ss]<<"\n";
                add(1,pre[i.ss],mxpre[i.ss],1,POT/2,i.ff);
                
            }
            else{
                ll a=zap[i.ss].ff.ff;
                ll b=zap[i.ss].ff.ss;
                ll lc=lca(a,b);
                //cout<<a<<" "<<b<<" "<<lc<<"\n";
                pair<ll,ll>mj=dod(gt(a),ode(gt(b),dod(gt(lc),gt(lc))));
                //cout<<mj.ff<<" "<<mj.ss<<"x\n";
                if(mj.ff>iles[i.ss]){
                    kon[i.ss]=i.ff;
                    ilekup[i.ss]=mj.ss;
                    ilezap[i.ss]=mj.ff;
                }
                else{
                    if(i.ff==1e9){
                        ilekup[i.ss]=mj.ss;
                    ilezap[i.ss]=mj.ff;
                    }
                    pocz[i.ss]=i.ff+1;
                }

            }
        }
        //cout<<"\n";
    }
    //cout<<dpt[3]<<" ";
    for(ll i=0;i<q;i++){
       // cout<<ilezap[i]<<" "<<iles[i]<<" "<<pocz[i]<<"\n";
        ll x=max(0LL,(ilezap[i]-iles[i]+pocz[i]-1)/pocz[i]);
        //cout<<dpt[zap[i].ff.ff]<<" "<<dpt[zap[i].ff.ss]<<" "<<2*dpt[lca(zap[i].ff.ff,zap[i].ff.ss)]<<" "<<lca(zap[i].ff.ff,zap[i].ff.ss)<<" "<<zap[i].ff.ff<<"\n";
        ll y=(dpt[zap[i].ff.ff]+dpt[zap[i].ff.ss]-2*dpt[lca(zap[i].ff.ff,zap[i].ff.ss)]);
        //cout<<x<<" "<<y<<" "<<ilekup[i]<<"\n";
        x=y+x-ilekup[i];;
        if(x>ilez[i])cout<<-1<<"\n";
        else cout<<ilez[i]-x<<"\n"; 
    }
}

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