Submission #1012688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012688		JakobZorz	Closing Time (IOI23_closing)	C++17	100 / 100	467 ms	100644 KiB

closing

#include"closing.h"
#include<vector>
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include<map>
using namespace std;
typedef __int128 ll;

int n,x,y;
ll k;
vector<pair<int,int>>nodes[200000];
ll distx[200000];
ll disty[200000];

void dfs1(int node,int par,ll*dists){
    for(auto[ne,w]:nodes[node]){
        if(ne==par)
            continue;
        dists[ne]=dists[node]+w;
        dfs1(ne,node,dists);
    }
}

int lvl1(){
    vector<bool>vis(n);
    int res=0;
    ll kr=k;
    priority_queue<pair<ll,int>>q;
    q.push({0,x});
    q.push({0,y});
    vis[x]=true;
    vis[y]=true;
    while(q.size()){
        int node=q.top().second;
        ll cost=-q.top().first;
        q.pop();
        if(cost>kr)
            break;
        res++;
        kr-=cost;
        for(auto[ne,w]:nodes[node]){
            if(vis[ne])
                continue;
            vis[ne]=true;
            q.push({-min(distx[ne],disty[ne]),ne});
        }
    }
    return res;
}

struct Tree{
    vector<ll>tree;
    int size;
    
    Tree(int n){
        size=1;
        while(size<n)
            size*=2;
        tree=vector<ll>(2*size);
    }
    
    Tree()=default;
    
    void upd(int i,ll x){
        i+=size;
        tree[i]=x;
        while(i!=1){
            i/=2;
            tree[i]=tree[2*i]+tree[2*i+1];
        }
    }
    
    int bound(int node,int rl,int rr,ll v){
        if(rl==rr-1){
            if(tree[node]<=v)
                return rr;
            return rl;
        }
        
        int mid=(rl+rr)/2;
        if(tree[2*node]<=v){
            return bound(2*node+1,mid,rr,v-tree[2*node]);
        }else{
            return bound(2*node,rl,mid,v);
        }
    }
    
    ll sum(int node,int rl,int rr,int x){
        if(rr<=x)
            return tree[node];
        if(x<=rl)
            return 0;
        int mid=(rl+rr)/2;
        return sum(2*node,rl,mid,x)+sum(2*node+1,mid,rr,x);
    }
    
    int bound(ll v){
        return bound(1,0,size,v);
    }
    
    ll sum(int x){
        return sum(1,0,size,x);
    }
};

struct Structure{
    vector<ll>vec;
    Tree tree;
    Tree pres;
    map<ll,int>mp;
    
    void reg(ll a){
        vec.push_back(a);
    }
    
    void init(){
        sort(vec.begin(),vec.end());
        tree=Tree((int)vec.size());
        pres=Tree((int)vec.size());
        for(int i=(int)vec.size()-1;i>=0;i--)
            mp[vec[i]]=i;
    }
    
    int get(ll money){
        return pres.sum(tree.bound(money));
    }
    
    void insert(ll a){
        tree.upd(mp[a],vec[mp[a]]);
        pres.upd(mp[a],1);
        mp[a]++;
    }
    
    void remove(ll a){
        mp[a]--;
        tree.upd(mp[a],0);
        pres.upd(mp[a],0);
    }
};

int cmp(pair<ll,ll>a,pair<ll,ll>b){
    return a.first+a.second<b.first+b.second;
}

int solve(vector<pair<ll,ll>>opts,ll money){
    sort(opts.begin(),opts.end(),cmp);
    Structure s;
    
    for(auto[i,j]:opts){
        s.reg(i);
        s.reg(j);
    }
    
    s.init();
    
    for(auto[i,j]:opts)
        s.insert(i);
    
    int res=s.get(money);
    int res2=0;
    for(auto[i,j]:opts){
        money-=i;
        s.remove(i);
        s.insert(j);
        res2++;
        if(money<0)
            break;
        res=max(res,res2+s.get(money));
    }
    return res;
}

int lvl2(){
    int cres=0;
    ll money=k;
    vector<pair<ll,ll>>opts;
    for(int i=0;i<n;i++){
        if(distx[i]+disty[i]==distx[y]){ // is on the path from x to y
            cres++;
            money-=min(distx[i],disty[i]);
            opts.emplace_back(max(distx[i],disty[i])-min(distx[i],disty[i]),1e18);
        }else{
            opts.emplace_back(min(distx[i],disty[i]),max(distx[i],disty[i])-min(distx[i],disty[i]));
        }
    }
    if(money<0)
        return 0;
    
    return cres+solve(opts,money);
}

int max_score(int N,int X,int Y,long long K,vector<int>U,vector<int>V,vector<int>W){
    n=N;
    x=X;
    y=Y;
    k=K;
    for(int i=0;i<n;i++){
        distx[i]=0;
        disty[i]=0;
        nodes[i].clear();
    }
    for(int i=0;i<n-1;i++){
        nodes[U[i]].emplace_back(V[i],W[i]);
        nodes[V[i]].emplace_back(U[i],W[i]);
    }
    dfs1(x,x,distx);
    dfs1(y,y,disty);
    
    return max(lvl1(),lvl2());
}

• 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