Submission #1209318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209318		user736482	Closing Time (IOI23_closing)	C++20	100 / 100	191 ms	38560 KiB

closing

#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 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

#include <bits/stdc++.h>
using namespace std;
ll dst1[200007],dst2[200007];
vector<pair<ll,ll>>g[200007];
void dfs1(ll v,ll pop,ll dst){
    dst1[v]=dst;
    for(pair<ll,ll> i : g[v]){
        if(i.ff!=pop){
            dfs1(i.ff,v,dst+i.ss);
        }
    }
}
void dfs2(ll v,ll pop,ll dst){
    dst2[v]=dst;
    for(pair<ll,ll> i : g[v]){
        if(i.ff!=pop){
            dfs2(i.ff,v,dst+i.ss);
        }
    }
}
int max_score(int n,int x,int y,ll k,vector<int>u,vector<int>v,vector<int>w){
    for(ll i=0;i<n+7;i++){
        g[i].clear();
    }
    for(ll i=0;i<n-1;i++){
        g[u[i]].pb({v[i],w[i]});
        g[v[i]].pb({u[i],w[i]});
    }
    dfs1(x,-1,0);
    dfs2(y,-1,0);
    vector<ll>v1,v3;
    vector<pair<ll,ll>>v2;
    ll K=k;
    ll dod=0;
    for(ll i=0;i<n;i++){
        v3.pb(min(dst1[i],dst2[i]));
        if(dst1[i]+dst2[i]==dst2[x]){
            //cout<<i<<" ";
            v1.pb(max(dst1[i],dst2[i])-min(dst1[i],dst2[i]));
            dod++;
            K-=min(dst1[i],dst2[i]);
        }
        else{
            if(min(dst1[i],dst2[i])*2<=max(dst1[i],dst2[i])){
                v1.pb(min(dst1[i],dst2[i]));
                v1.pb(max(dst1[i],dst2[i])-min(dst1[i],dst2[i]));
            }
            else{
                v2.pb({max(dst1[i],dst2[i]),min(dst1[i],dst2[i])});
            }
        }
    }
    ll wyn1=0;
    ll pom=k;
    //cout<<k<<" ";
    sort(v3.begin(),v3.end());
    for(ll i=0;i<n;i++){
        if(pom-v3[i]<0)break;
        pom-=v3[i];
        //cout<<"xd";
        wyn1++;
    }
    if(K<0)return wyn1;
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());

    multiset<ll>s1,s2;
    ll ak=v2.size();//pierwszy niewiziety
    ll akwyn=2*v2.size()+dod-1;
    for(pair<ll,ll> i : v2){
        K-=i.ff;
        s1.insert(i.ff-i.ss);
    }
    for(ll i=0;i<=v1.size();i++){
        if(i){
            K-=v1[i-1];
        }
        akwyn++;
        while(K<0){
            if(ak==0)return wyn1;
            akwyn-=2;
            K+=v2[--ak].ff;
            s1.erase(s1.lower_bound(v2[ak].ff-v2[ak].ss));
            s2.insert(v2[ak].ss);
        }
        ll czy=0;
        if(s2.size() && *s2.begin()<=K)czy=1;
        if(s1.size() && ak<v2.size() && (*--s1.end())+K>=v2[ak].ff)czy=1;
        wyn1=max(wyn1,akwyn+czy);
    }
    return wyn1;
}

• 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