Submission #839907

#	Time	Username	Problem	Language	Result	Execution time	Memory
839907		jtnydv25	Closing Time (IOI23_closing)	C++17	44 / 100	106 ms	26316 KiB

closing

#include "closing.h"

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

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

int max_score(int n, int x, int y, ll K, vector<int> U, vector<int> V, vector<int> W){
    const ll INF = 2e18;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n - 1; i++){
        adj[U[i]].push_back(i);
        adj[V[i]].push_back(i);
    }
    function<vector<ll>(int)> getDists = [&](int a){
        vector<int> vis(n);
        vector<ll> D(n);
        function<void(int, int)> dfs = [&](int s, int p){
            for(int i: adj[s]){
                int v = U[i] ^ V[i] ^ s;
                if(v == p) continue;
                int w = W[i];
                D[v] = D[s] + w;
                dfs(v, s);
            }
        };
        dfs(a, a);
        return D;
    };
    vector<ll> X = getDists(x), Y = getDists(y);
    vector<ll> lft, rgt1, rgt2;
    vector<bool> isInside(n);
    vector<int> inside;
    for(int i = 0; i < n; i++){
        isInside[i] = (X[i] + Y[i] == X[y]);
        if(isInside[i]){
            inside.push_back(i);
        }
    }
    sort(all(inside), [&](int i, int j){return min(X[i], Y[i]) < min(X[j], Y[j]);});
    int num = 0;
    for(int i: inside){
        ll u = min(X[i],Y[i]);
        if(u <= K){
            K -= u;
            num++;
        } else{
            return num;
        }
    }
    
    vector<ll> vals;
    
    for(int i = 0; i < n; i++){
        ll u = min(X[i], Y[i]), v = max(X[i], Y[i]);
        if(isInside[i]){
            lft.push_back(v - u);
            continue;
        }
        if(v >= 2 * u){
            lft.push_back(u);
            lft.push_back(v - u);
        } else{
            rgt1.push_back(u);
            rgt2.push_back(v);
        }
    }
    int k = sz(rgt1);
    vector<int> perml(sz(lft)), permr(k);
    sort(all(lft));
    iota(all(permr), 0);
    sort(all(permr), [&](int i, int j){return rgt2[i] < rgt2[j];});
    vector<ll> suffixes(k + 1, INF);
    for(int i = k - 1; i >= 0; i--) suffixes[i] = min(suffixes[i + 1], rgt1[permr[i]]);
    vector<ll> minCost(2 * k + 1, INF);
    minCost[0] = 0;
    ll pref = 0;
    ll bestDiff = INF;
    for(int i = 0; i < k; i++){
        minCost[2 * i + 1] = min(minCost[2 * i + 1], pref + suffixes[i]);
        int pos  = permr[i];
        bestDiff = min(bestDiff, rgt1[pos] - rgt2[pos]);
        pref += rgt2[pos];
        minCost[2 * (i + 1)] = pref;
        minCost[2 * i + 1] = min(minCost[2 * i + 1], pref + bestDiff);
    }
    int lo = 0, hi = 2 * n - num;
    while(lo < hi){
        int mid = (lo + hi + 1) / 2;
        ll sum = 0;
        bool ok = false;
        for(int i = 0; i <= sz(lft) && i <= mid; i++){
            int rem = mid - i;
            
            if(rem <= 2 * k && sum + minCost[rem] <= K){
                ok = true;
            }
            if(i != sz(lft)) sum += lft[i];
        }
        if(ok) lo = mid;
        else hi = mid - 1;
    }
    return lo + num;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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