Submission #1216390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216390		ASGA_RedSea	Closing Time (IOI23_closing)	C++17	52 / 100	804 ms	49060 KiB

closing

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

#include"closing.h"

int max_score(int n,int x,int y,ll k,vector<int>U,vector<int>V,vector<int>W);


struct sgt{
    vector<ll>s,c;
    int lg,sz;
    sgt(int n){
        lg=__lg(n)+1;
        sz=1<<lg;
        s.assign(sz*2,0);c=s;
    }
    void add(int i,ll v){
        i+=sz;
        s[i]+=v;
        c[i]=1;
        while(i>1){
            i>>=1;
            s[i]=s[i*2]+s[i*2+1];
            c[i]=c[i*2]+c[i*2+1];
        }
    }
    void del(int i){
        i+=sz;s[i]=c[i]=0;
        while(i>1){
            i>>=1;
            s[i]=s[i*2]+s[i*2+1];
            c[i]=c[i*2]+c[i*2+1];
        }
    }
    ll get(ll L,ll R,ll l,ll r,ll i){
        if(l>R||L>r)return 0;
        if(L<=l&&r<=R)return c[i];
        return get(L,R,l,(l+r)/2,i*2)+get(L,R,(l+r)/2+1,r,i*2+1);
    }
    ll get(ll k){
        ll i=1,tot=0;
        while(i<sz){
            if(tot+s[i*2]<=k){tot+=s[i*2];i=i*2+1;}
            else i*=2;
        }
        if(s[i]+tot<=k)i++;

        return get(1,i-sz,1,sz,1);
    }
};

const ll inf=1e18;




int max_score(int n,int x,int y,ll k,vector<int>U,vector<int>V,vector<int>W){
    vector<vector<array<ll,2>>>a(n);
    int sbt=1;
    for(int i=0;i+1<n;i++){
        a[U[i]].push_back({V[i],W[i]});
        a[V[i]].push_back({U[i],W[i]});
        sbt&=V[i]==U[i]+1;
    }

    ll ans=0;

    queue<int>q;
    vector<array<ll,2>>d(n,{inf,inf});

    d[x][0]=0;q.push(x);
    while(!q.empty()){
        int i=q.front();q.pop();
        for(auto&[j,w]:a[i]){
            if(d[j][0]==inf){d[j][0]=d[i][0]+w;q.push(j);}
        }
    }
    d[y][1]=0;q.push(y);
    while(!q.empty()){
        int i=q.front();q.pop();
        for(auto&[j,w]:a[i]){
            if(d[j][1]==inf){d[j][1]=d[i][1]+w;q.push(j);}
        }
    }

    vector<int>vis(n,0);
    multiset<array<ll,2>>s;
    for(int i=0;i<n;i++){
        s.insert({d[i][0],i});
        s.insert({d[i][1],i});
    }

    ll kk=k;
    for(int cnt=0;cnt<n;cnt++){
        ll i=(*s.begin())[1],c=(*s.begin())[0];
        s.erase(s.find(*s.begin()));
        if(vis[i]||c>kk)break;
        vis[i]++;
        kk-=c;ans++;
    }


    if(sbt){
        vector<ll>p(n,0);
        for(int i=0;i+1<n;i++)p[i+1]=p[i]+a[i][(a[i][1][0]==i+1)][1];

        auto dis=[&](int i,int j)->ll{
            if(i>j)swap(i,j);
            return p[j]-p[i];
        };

        for(int l=0;l<=y;l++){
            int r=max(x,l);

            ll v=0;

            for(int i=l;i<=r;i++)v+=max(dis(i,x),dis(i,y));
            for(int i=r+1;i<=y;i++)v+=dis(i,y);
            for(int i=x;i<l;i++)v+=dis(i,x);



            vector<array<ll,2>>vl;
            for(int i=0;i<min(l,x);i++)vl.push_back({dis(i,x),i});
            for(int i=max(y,r)+1;i<n;i++)vl.push_back({dis(i,y),i});

            sort(vl.begin(),vl.end());
            vector<int>val(n);
            for(int i=0;i<vl.size();i++)val[vl[i][1]]=i;


            sgt s(vl.size());
            for(int i=0;i<vl.size();i++)s.add(i,vl[i][0]);


            if(v<=k)ans=max(ans,(r-l+1)*2+max(0,l-x)+max(0,y-r)+s.get(k-v));


            while(++r<n){
                if(r<=y)v+=max(0LL,dis(r,x)-dis(r,y));
                else v+=dis(r,x);


                if(r>y)s.del(val[r]);
                if(v<=k)ans=max(ans,(r-l+1)*2+max(0,l-x)+max(0,y-r)+s.get(k-v));
            }
        }


        return ans;
    }

    if(d[y][0]<=2*k){
        bool v[25],ff[25]{};
        vector<ll>q;
        vector<bool>f[25];

        vector<int>c;
        auto calc=[&](int i,int p,auto&calc)->void{
            c.push_back(i);

            if(v[i]){
                for(int i=c.size()-1;i>=0&&ff[c[i]]==0;i--)ff[c[i]]=1;
            }

            for(auto&[j,k]:a[i])if(j!=p)calc(j,i,calc);

            c.pop_back();
        };


        for(int i=0;i<(1<<n);i++){
            for(int j=0;j<n;j++)v[j]=(i>>j)&1;

            calc(x,-1,calc);
            for(int j=0;j<n;j++)if(ff[j]){f[j].push_back(0);ff[j]=0;}

            calc(y,-1,calc);
            for(int j=0;j<n;j++)if(ff[j]){f[j].push_back(1);ff[j]=0;}

            ll tot=0,mx;
            for(int j=0;j<n;j++){
                mx=0;
                for(const int&jj:f[j])mx=max(mx,d[j][jj]);
                tot+=mx;
            }

            if(tot<=k){
                ll kk=k-tot,aans=0;
                q.clear();
                for(int j=0;j<n;j++){
                    if(f[j].empty()){
                        q.push_back(min(d[j][0],d[j][1]));
                    }
                    aans+=f[j].size();
                }
                sort(q.begin(),q.end());
                for(int ii=0;ii<q.size()&&kk>=q[ii];ii++){
                    kk-=q[ii];aans++;
                }
                ans=max(aans,ans);
            }

            for(int j=0;j<n;j++)f[j].clear();
        }
    }


    return ans;
}

• 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: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17