Submission #1159613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159613		duccnamm	Two Currencies (JOI23_currencies)	C++20	100 / 100	3690 ms	50008 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,q,uu[100005],vv[100005],p[100005],child[100005],h[100005],par[100005],in[100005],out[100005],chainhead[100005],chainid[100005],timehld,timedfs,f[400005],l[100005],r[100005],dd,s[100005],t[100005],x[100005],y[100005],vc[100005],pp[100005];
vector<ll>a[100005];
vector<ll>que[100005];
pair<ll,ll>c[100005];
void dfsmake(ll x,ll pa)
{
    child[x]=1;
    for(auto it:a[x])
        if(it!=pa)
        {
            h[it]=h[x]+1;
            par[it]=x;
            dfsmake(it,x);
            child[x]+=child[it];
        }
}
void dfshld(ll x,ll pa)
{
    if(chainhead[timehld]==0)
        chainhead[timehld]=x;
    chainid[x]=timehld;
    timedfs++;
    in[x]=timedfs;
    ll heavy=0;
    for(auto it:a[x])
        if(it!=pa)
            if(heavy==0||child[it]>child[heavy])heavy=it;
    if(heavy!=0)dfshld(heavy,x);
    for(auto it:a[x])
        if(it!=pa&&it!=heavy)
        {
            timehld++;
            dfshld(it,x);
        }
    out[x]=timedfs;
    return;
}
ll getlca(ll x,ll y)
{
    while(chainid[x]!=chainid[y])
    {
        if(chainid[x]>chainid[y])
            x=par[chainhead[chainid[x]]];
        else
            y=par[chainhead[chainid[y]]];
    }
    if(h[x]<h[y])return x;
    return y;
}
void update(ll id,ll l,ll r,ll i,ll v)
{
    if(i<l||i>r)
        return;
    if(l==r)
    {
        f[id]+=v;
        return;
    }
    ll mid=(l+r)/2;
    update(id*2,l,mid,i,v);
    update(id*2+1,mid+1,r,i,v);
    f[id]=f[id*2]+f[id*2+1];
}
ll getsum(ll id,ll l,ll r,ll u,ll v)
{
    if(l>r)return 0;
    if(v<l||r<u)return 0;
    if(u<=l&&v>=r)return f[id];
    ll mid=(l+r)/2;
    return getsum(id*2,l,mid,u,v)+getsum(id*2+1,mid+1,r,u,v);
}
ll getquery(ll u,ll v)
{
    ll lca=getlca(u,v);
    ll ans=0;
    while(chainid[u]!=chainid[lca])
    {
        ans+=getsum(1,1,n,in[chainhead[chainid[u]]],in[u]);
        u=par[chainhead[chainid[u]]];
    }
    while(chainid[v]!=chainid[lca])
    {
        ans+=getsum(1,1,n,in[chainhead[chainid[v]]],in[v]);
        v=par[chainhead[chainid[v]]];
    }
    if(h[u]<h[v])
        ans+=getsum(1,1,n,in[u]+1,in[v]);
    else
        ans+=getsum(1,1,n,in[v]+1,in[u]);
    return ans;
}
void dfssl(ll x,ll pa)
{
    for(ll it:a[x])
        if(it!=pa)
        {
            pp[it]+=pp[x];
            dfssl(it,x);
        }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        cin>>uu[i]>>vv[i];
        a[uu[i]].push_back(vv[i]);
        a[vv[i]].push_back(uu[i]);
    }
    dfsmake(1,0);
    dfshld(1,0);
    for(int i=1;i<=m;i++)
    {
        cin>>c[i].second>>c[i].first;
        c[i].second=max(in[vv[c[i].second]],in[uu[c[i].second]]);
    }
    sort(c+1,c+m+1);
    for(int i=1;i<=q;i++)
    {
        cin>>s[i]>>t[i]>>x[i]>>y[i];
        l[i]=1;
        r[i]=m;
        vc[i]=0;
    }
    while(1)
    {
        dd=0;
        for(int i=1;i<=q;i++)
            if(l[i]<=r[i])
            {
                que[(l[i]+r[i])/2].push_back(i);
                dd++;
            }
        if(dd==0)
            break;
        for(int i=1;i<=4*n;i++)
            f[i]=0;
        for(ll i=1;i<=m;i++)
        {
            update(1,1,n,c[i].second,c[i].first);
            for(ll it:que[i])
            {
                dd=getquery(s[it],t[it]);
//                cout<<s[it]<<" "<<t[it]<<'\n';
//                cout<<it<<" "<<i<<" "<<dd<<'\n';
                if(y[it]>=dd)
                {
                    l[it]=i+1;
                    vc[it]=max(vc[it],i);
                }
                else
                    r[it]=i-1;
            }
            que[i].clear();
        }
    }
    for(int i=1;i<=q;i++)
        que[vc[i]].push_back(i);
    for(int i=1;i<=4*n;i++)
        f[i]=0;
    for(int i=1;i<=m;i++)
    {
        update(1,1,n,c[i].second,1);
        for(ll it:que[i])
            vc[it]=getquery(s[it],t[it]);
        que[i].clear();
    }
    for(int i=1;i<=q;i++)
    {
        dd=getquery(s[i],t[i]);
        dd-=vc[i];
        if(x[i]>=dd)
            cout<<x[i]-dd<<'\n';
        else
            cout<<-1<<'\n';
    }
    return 0;
}

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