Submission #846518

#	Time	Username	Problem	Language	Result	Execution time	Memory
846518		onepunchac168	Closing Time (IOI23_closing)	C++17	100 / 100	394 ms	53320 KiB

closing

#include "closing.h" // do not change this

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair <ll,ll > ii;
typedef pair <ii,ll> iii;
const char nl= '\n';
const int Na=2e5+5;
int n,x,y;
ll k;
vector <ii> vt[Na];
ll res=0;
ll dp[Na][2];
bool cp[Na];
void dijkstra(int u,int dd)
{
    priority_queue<ii,vector <ii>,greater <ii> > qu;
    for (int i=0; i<n; i++)
    {
        dp[i][dd]=1e18+5;
        cp[i]=0;
    }
    dp[u][dd]=0;
    qu.push({0,u});
    while (!qu.empty())
    {
        ii aa=qu.top();
        qu.pop();
        if (cp[aa.se]==1)
        {
            continue;
        }
        cp[aa.se]=1;
        for (auto v:vt[aa.se])
        {
            if (dp[v.fi][dd]>dp[aa.se][dd]+v.se)
            {
                dp[v.fi][dd]=dp[aa.se][dd]+v.se;
                qu.push({dp[v.fi][dd],v.fi});
            }
        }
    }
}
void solve1()
{
    dijkstra(x,0);
    dijkstra(y,1);
    vector <ll> cnt;
    for (int i=0; i<n; i++)
    {
        cnt.pb(min(dp[i][0],dp[i][1]));
    }
    ll ans=0;
    ll dem=0;
    sort (cnt.begin(),cnt.end());
    for (auto v:cnt)
    {
        if (dem+v<=k)
        {
            dem+=v;
            ans++;
        }
        else break;
    }
    res=ans;
}
bool check[Na];
void dfs(int u,int vv)
{
    if (u==y)
    {
        check[u]=1;
        return;
    }
    for (auto v:vt[u])
    {
        if (v.fi==vv)
        {
            continue;
        }
        dfs(v.fi,u);
        if (check[v.fi]==1)
        {
            check[u]=1;
        }
    }
}
/*const int M=3005;
ll dpa[M][M*2];
void solve2()
{
    for (int i=0;i<n;i++)
    {
        check[i]=0;
    }
    dfs(x,-1);
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<=2*n;j++)
        {
            dpa[i][j]=1e18+5;
        }
    }
    if (check[0]==1)
    {
        dpa[0][1]=min(dp[0][1],dp[0][0]);
        dpa[0][2]=max(dp[0][1],dp[0][0]);
    }
    else
    {
        dpa[0][0]=0;
        dpa[0][1]=min(dp[0][1],dp[0][0]);
        dpa[0][2]=max(dp[0][1],dp[0][0]);
    }
    for (int i=1;i<n;i++)
    {
        for (int j=0;j<=2*(i+1);j++)
        {
            if (check[i]==1)
            {
                if (j>=1){
                    dpa[i][j]=min(dpa[i][j],min(dp[i][0],dp[i][1])+dpa[i-1][j-1]);
                }
                if (j>=2)
                {
                    dpa[i][j]=min(dpa[i][j],max(dp[i][0],dp[i][1])+dpa[i-1][j-2]);
                }
            }
            else
            {
                dpa[i][j]=dpa[i-1][j];
                if (j>=1){
                    dpa[i][j]=min(dpa[i][j],min(dp[i][0],dp[i][1])+dpa[i-1][j-1]);
                }
                if (j>=2)
                {
                    dpa[i][j]=min(dpa[i][j],max(dp[i][0],dp[i][1])+dpa[i-1][j-2]);
                }
            }
        }
    }
    for (int j=0;j<=2*n;j++)
    {
        //cout<<j<<" "<<dpa[n][j]<<" "<<k<<nl;
        if (dpa[n-1][j]<=k)
        {
            res=max(res,j);
        }
    }
}*/
ii T[8*Na];
void build (int node,int l,int r)
{
    if (l==r)
    {
        T[node]= {0,0};
        return;
    }
    build(node*2,l,(l+r)/2);
    build(node*2+1,(l+r)/2+1,r);
    T[node]= {0,0};
}
void update(int node,int l,int r,int u,ii val)
{
    if (l>u||r<u)
    {
        return;
    }
    if (l==r)
    {
        T[node].fi+=val.fi;
        T[node].se+=val.se;
        return;
    }
    update(node*2,l,(l+r)/2,u,val);
    update(node*2+1,(l+r)/2+1,r,u,val);
    T[node].fi=T[node*2].fi+T[node*2+1].fi;
    T[node].se=T[node*2].se+T[node*2+1].se;
}
ll sum;
ii query(int node,int l,int r,ll val)
{
    //cout<<l<<" "<<r<<" "<<T[node].se<<nl;
    if (l==r)
    {
        sum+=T[node].fi;
        return {T[node].se,l};
    }
    int mid=(l+r)/2;
    if (T[node*2].fi<val)
    {
        sum+=T[node*2].fi;
        ii bb=query(node*2+1,mid+1,r,val-T[node*2].fi);
        return {bb.fi+T[node*2].se,bb.se};
    }
    ii bb=query(node*2,l,mid,val);
    return bb;
}
void solve3()
{
    vector <ll> tmp;
    for (int i=0; i<n; i++)
    {
        check[i]=0;
    }
    dfs(x,-1);
    ll resa=0;
    ll dem=0;
    vector <ii> gg;
    for (int i=0; i<n; i++)
    {
        if (check[i]==1)
        {
            resa+=min(dp[i][0],dp[i][1]);
            tmp.pb(abs(dp[i][0]-dp[i][1]));
            dem++;
        }
        else
        {
            tmp.pb(min(dp[i][0],dp[i][1]));
            tmp.pb(abs(dp[i][0]-dp[i][1]));
            gg.pb({max(dp[i][0],dp[i][1]),i});
        }
    }
    sort (gg.begin(),gg.end());
    sort (tmp.begin(),tmp.end());
    tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
    build(1,1,tmp.size());
    if (resa>k)
    {
        return;
    }
    for (int i=0; i<n; i++)
    {
        if (check[i]==1)
        {
            ll aa=lower_bound(tmp.begin(),tmp.end(),abs(dp[i][0]-dp[i][1]))-tmp.begin()+1;
            update(1,1,tmp.size(),aa, {abs(dp[i][0]-dp[i][1]),1});
        }
        else
        {
            ll aa=lower_bound(tmp.begin(),tmp.end(),min(dp[i][0],dp[i][1]))-tmp.begin()+1;
            update(1,1,tmp.size(),aa, {min(dp[i][0],dp[i][1]),1});
        }
    }
    ll ans=0;
    {
        ll h2=0;
        sum=0;
        ii h1=query(1,1,tmp.size(),k-resa);
        h2=h1.fi;
        ll gg=tmp[h1.se-1];
        if (sum>k-resa)
        {
            ll rr=(sum-k+resa)/gg;
            if (rr*gg<sum-k+resa)
            {
                rr++;
            }
            h2-=rr;
        }
        res=max(res,ans+dem+h2);
    }
    for (auto v:gg)
    {
        ans++;
        ll aa=lower_bound(tmp.begin(),tmp.end(),min(dp[v.se][0],dp[v.se][1]))-tmp.begin()+1;
        update(1,1,tmp.size(),aa, {-min(dp[v.se][0],dp[v.se][1]),-1});
        ll bb=lower_bound(tmp.begin(),tmp.end(),abs(dp[v.se][0]-dp[v.se][1]))-tmp.begin()+1;
        update(1,1,tmp.size(),bb, {abs(dp[v.se][0]-dp[v.se][1]),1});
        //cout<<v.se<<" "<<abs(dp[v.se][0]-dp[v.se][1])<<nl;
        resa+=min(dp[v.se][0],dp[v.se][1]);
        if (resa<=k)
        {
            ll h2=0;
            sum=0;
            ii h1=query(1,1,tmp.size(),k-resa);
            h2=h1.fi;
            ll gg=tmp[h1.se-1];
            if (sum>k-resa)
            {
                ll rr=(sum-k+resa)/gg;
                if (rr*gg<sum-k+resa)
                {
                    rr++;
                }
                h2-=rr;

            }
            res=max(res,ans+dem+h2);
            //cout<<sum-k+resa<<" "<<res<<" "<<ans+dem+h2<<" "<<ans<<" "<<dem<<" "<<h2<<" "<<k-resa<<nl;
        }
    }

}
ll dema=0;
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n=N;
    x=X;
    y=Y;
    k=K;
    res=0;
    dema+=N;
    for (int i=0; i<n; i++)
    {
        vt[i].clear();
    }
    for (int i=0; i<n-1; i++)
    {
        vt[U[i]].pb({V[i],W[i]});
        vt[V[i]].pb({U[i],W[i]});
    }
    solve1();
    /*if (n<=3000&&dema<=3000){
        solve2();
    }*/
    solve3();
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17