Submission #1248585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248585		Boomyday	Closing Time (IOI23_closing)	C++20	8 / 100	104 ms	34492 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e18;
vector<ll> distx, disty;
vector<vector<pair<ll,int>>> adj;

void get_dist(vector<ll>& dist, int u, int p = -1){
    for(auto& [w, v]:adj[u]) if (v != p){
        dist[v] = dist[u] + w;
        get_dist(dist, v, u);
    }

}


vector<ll> c1;
vector<pair<ll,ll>> c2;
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    adj.clear();
    adj.resize(N);
    for(int i=0;i<N-1;++i){
        adj[U[i]].push_back({W[i], V[i]});
        adj[V[i]].push_back({W[i], U[i]});
    }

    distx.resize(N); disty.resize(N);
    distx[X] = 0;
    disty[Y] = 0;
    get_dist(distx, X);
    get_dist(disty, Y);



    // solve the first subtask
    int ans = 0;

    vector<ll> dists;

    for(int i=0;i<N;++i) dists.push_back(min(distx[i], disty[i]));

    sort(dists.begin(), dists.end());
    ll kk = K;
    for(auto&d:dists){
        if (kk < d) break;
        ans += 1;
        kk -= d;
    }

    // now time to try and get a better answer using greed approach
    kk = K;
    ll D = distx[Y];

    vector<bool> is_path(N, 0);
    for(int i=0;i<N;++i){
        if (distx[i] + disty[i] == D){
            // this is a critical node
            if (distx[i] > disty[i]){
                // far from x, connect to y
                kk -= disty[i];
            } else {
                kk -= distx[i];
            }
            is_path[i] = 1;
        }
    } // visit all the good nodes once
    if (kk < 0) return ans;
    // now maintain the caches
    c1.clear(); c2.clear();

    for(int i=0;i<N;++i){
        ll dif = abs(distx[i]-disty[i]);
        if(is_path[i]){
            c1.push_back(0);
            c1.push_back(dif);
        }
        else {
            ll dst = min(distx[i], disty[i]);
            if (dst <= dif) {
                c1.push_back(dst);
                c1.push_back(dif);
            }
            else {
                c2.push_back({dst+dif, dst});
            }
        }
    }
    sort(c1.begin(), c1.end());
    sort(c2.begin(), c2.end());
    // next we compute suffix minimums
    vector<ll> suf_min(c2.size()+1, INF);

    for(int i=c2.size()-1;i>=0;--i){
        suf_min[i] = min(suf_min[i+1], c2[i].second);
    }


    // for twos taken there are 3 cases:
    // block of twos taken
    // block of 2s, 1, 2
    // block of 2s, suffix min.

    // case 1: block of twos

    ll taken = 0;
    int numones = 0;
    for(int i=0;i<c2.size();++i) {
        taken += c2[i].first;
    }

    for(int numtwos = c2.size();numtwos >= 0; numtwos--){
        if (taken > kk){
            taken -= c2[numtwos-1].first;
            continue;
        }
        // add ones
        while (numones < c1.size() && taken + c1[numones] <= kk){
            taken += c1[numones++];
        }
        ans = max(ans, numones + 2*numtwos);
    }

    // case 2: block of twos and a suffix minimum
    taken = 0;
    numones = 0;
    for(int i=0;i<c2.size();++i) {
        taken += c2[i].first;
    }
    taken += suf_min[c2.size()];

    for(int numtwos = c2.size();numtwos >= 0; numtwos--){
        if (taken > kk){
            if (numtwos == 0){
                break;
            }
            taken -= suf_min[numtwos];
            taken -= c2[numtwos-1].first;
            taken += suf_min[numtwos - 1];
            continue;
        }
        // add ones
        while (numones < c1.size() && taken + c1[numones] <= kk){
            taken += c1[numones++];
        }
        ans = max(ans, numones + 2*numtwos + 1);
    }

    if (c2.size() < 2) return ans;

    taken = 0;
    numones = 0;
    for(int i=0;i<c2.size()-2;++i){
        taken += c2[i].first;
    }
    taken += c2[c2.size()-2].second;
    taken += c2[c2.size()-1].first;

    // case 3: block of twos, one, two
    for(int numtwos = c2.size()-2;numtwos >= 0; numtwos--){
        if (taken > kk){
            if (numtwos == 0) break;
            taken -= c2[numtwos-1].first;
            taken -= c2[numtwos].second;
            taken -= c2[numtwos+1].first;
            taken += c2[numtwos-1].second;
            taken += c2[numtwos].first;
            continue;
        }
        // add ones
        while (numones < c1.size() && taken + c1[numones] <= kk){
            taken += c1[numones++];
        }
        ans = max(ans, numones + 2*numtwos + 3);

    }



    return ans;
}

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