Submission #1267063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267063		imarn	Closing Time (IOI23_closing)	C++20	73 / 100	111 ms	39752 KiB

closing

//#include "festival.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define sz(x) (ll)x.size()
#define cd complex<double>
#define t3 tuple<ll,ll,ll>
using namespace std;
const int mxn=2e5+5;
vector<pll>g[mxn];
ll d[2][mxn]{0};
int lvl[mxn]{0};
int core[mxn]{0};
void dfs(int i,int u,int p){
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        d[i][v]=d[i][u]+w;dfs(i,v,u);
    }
}multiset<pll>ms;
void clean(int n){
    for(int i=0;i<n;i++)g[i].clear(),d[0][i]=d[1][i]=lvl[i]=core[i]=0;
    ms.clear();
}
int max_score(int N, int X, int Y,ll K,vector<int>U,vector<int>V,vector<int>W){
    for(int i=0;i<N-1;i++)g[U[i]].pb({V[i],W[i]}),g[V[i]].pb({U[i],W[i]});
    dfs(0,X,X);dfs(1,Y,Y);ll sum=0;int rs1=0;ms.insert({0,-1});
    priority_queue<ll,vector<ll>,greater<ll>>pq;
    priority_queue<pll,vector<pll>,greater<pll>>q1,q2;
    for(int i=0;i<N;i++)pq.push(d[0][i]),pq.push(d[1][i]);
    while(!pq.empty()&&sum+pq.top()<=K){
        sum+=pq.top();rs1++;pq.pop();
    }for(int i=0;i<N;i++){
        if(d[0][i]>d[1][i])swap(d[0][i],d[1][i]);
        d[1][i]-=d[0][i];
    }sum=0;int rs2=0;
    for(int i=0;i<N;i++)if(2*d[0][i]+d[1][i]==d[1][X]){
        sum+=d[0][i],rs2++,lvl[i]=1,q1.push({d[1][i],i+1}),core[i]=1;
    }
    for(int i=0;i<N;i++)if(lvl[i]==0)q1.push({d[0][i],-(i+1)}),q2.push({d[0][i]+d[1][i],i+1});
    if(sum>K){clean(N);return rs1;}
    while(!q1.empty()||!q2.empty()){
        if(q2.empty()){
            auto [x,i]=q1.top();q1.pop();
            int lv=(i>0);i=abs(i);i--;
            if(lvl[i]!=lv)continue;
            if(sum+x>K){clean(N);return max(rs1,rs2);}sum+=x;rs2++;
            if(lvl[i]==0)lvl[i]=1,ms.insert({x,i}),q1.push({d[1][i],i+1});
            else if(lvl[i]==1){
                lvl[i]=2;
                if(!core[i])ms.erase({d[0][i],i});
                ms.insert({x,i});
            }
        }
        else if(q1.empty()){
            auto [x,i]=q2.top();q2.pop();i--;
            if(lvl[i]!=0)continue;
            if(sum+x>K){clean(N);return max(rs1,rs2);}sum+=x;rs2+=2;
            lvl[i]=2;ms.insert({d[1][i],i});
        }
        else if(q1.top().f<q2.top().f-(--ms.end())->f){
            auto [x,i]=q1.top();q1.pop();
            int lv=(i>0);i=abs(i);i--;
            if(lvl[i]!=lv)continue;
            if(sum+x>K){clean(N);return max(rs1,rs2);}sum+=x;rs2++;
            if(lvl[i]==0)lvl[i]=1,ms.insert({x,i}),q1.push({d[1][i],i+1});
            else if(lvl[i]==1){
                lvl[i]=2;
                if(!core[i])ms.erase({d[0][i],i});
                ms.insert({x,i});
            }
        }
        else {
            auto [x,i]=q2.top();q2.pop();i--;
            if(lvl[i]!=0)continue;
            if(sum+x-(--ms.end())->f>K){clean(N);return max(rs1,rs2);}sum+=x-(--ms.end())->f;rs2++;
            auto it = (--ms.end());
            if(lvl[it->s]==1){
                lvl[it->s]=0;
                q1.push({d[0][it->s],-it->s-1});
                q2.push({d[0][it->s]+d[1][it->s],it->s+1});
                ms.erase(it);
            }
            else if(lvl[it->s]==2){
                lvl[it->s]=1;
                q1.push({d[1][it->s],it->s+1});
                if(!core[i])ms.insert({d[0][it->s],it->s});
                ms.erase(it);
            }
            lvl[i]=2;ms.insert({d[1][i],i});
        }
    }clean(N);
    return max(rs1,rs2);
}
/*int main(){
    cout<<max_score(7, 0, 2, 10,{0, 0, 1, 2, 2, 5},{1, 3, 2, 4, 5, 6},{2, 3, 4, 2, 5, 3});
}*/

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