Submission #843988

#	Time	Username	Problem	Language	Result	Execution time	Memory
843988		Lucpp	Closing Time (IOI23_closing)	C++17	100 / 100	231 ms	43992 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
using ll = long long;
constexpr ll inf = 2e18;

ll maxCost;
vector<vector<pair<int, ll>>> g;

int solveGreedy(int X, int Y){
    priority_queue<tuple<ll, int, int>> pq;
    pq.emplace(0, X, X);
    pq.emplace(0, Y, Y);
    ll remain = maxCost;
    int score = 0;
    while(remain >= 0 && !pq.empty()){
        auto [c, u, p] = pq.top(); pq.pop();
        if(remain + c < 0) break;
        remain += c;
        score++;
        for(auto [v, w] : g[u]){
            if(v != p) pq.emplace(c-w, v, u);
        }
    }
    return score;
}

vector<int> par;
vector<ll> dist;
vector<pair<ll, ll>> costs;

void dfs(int u){
    for(auto [v, w] : g[u]){
        if(v == par[u]) continue;
        par[v] = u;
        dist[v] = dist[u]+w;
        dfs(v);
    }
}

void collect(int u, ll myDist, ll upgrade){
    costs.emplace_back(myDist, myDist+upgrade);
    for(auto [v, w] : g[u]){
        if(v == par[u]) continue;
        collect(v, myDist+w, upgrade);
    }
}

int solve(){
    vector<ll> sing;
    vector<pair<ll, ll>> doub;
    for(auto [c1, c2] : costs){
        if(c1 <= c2-c1) sing.push_back(c1), sing.push_back(c2-c1);
        else doub.emplace_back(c1, c2);
    }
    sort(sing.begin(), sing.end());
    sort(doub.begin(), doub.end(), [](pair<ll, ll> p, pair<ll, ll> q){return p.second < q.second;});
    int p = (int)sing.size() - 1;
    ll s = accumulate(sing.begin(), sing.end(), 0ll);
    int ans = 0;
    auto upd = [&](int cnt, ll x){
        if(x > maxCost) return;
        while(s+x > maxCost){
            s -= sing[p--];
        }
        ans = max(ans, p + 1 + cnt);
    };
    upd(0, 0);
    int n = (int)doub.size();
    multiset<ll> add, sub;
    for(auto [c1, c2] : doub) add.insert(c1);
    ll co = 0;
    for(int i = 0; i < n; i++){
        ll y = co + *add.begin();
        co += doub[i].second;
        sub.insert(doub[i].second - doub[i].first);
        y = min(y, co - *sub.rbegin());
        upd(2*i+1, y);
        upd(2*i+2, co);
        add.erase(add.find(doub[i].first));
    }
    return ans;
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
    costs.clear();
    maxCost = K;
    g.clear();
    g.resize(N);
    for(int i = 0; i < N-1; i++){
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
    par.assign(N, -1);
    dist.assign(N, 0);
    dfs(X);
    int ans = solveGreedy(X, Y);
    int u = Y, last = -1;
    while(u != -1){
        ll d1 = dist[u], d2 = dist[Y]-dist[u];
        ll myDist = min(d1, d2), upgrade = abs(d1-d2);
        costs.emplace_back(0, upgrade);
        maxCost -= myDist;
        for(auto [v, w] : g[u]){
            if(v == par[u] || v == last) continue;
            collect(v, myDist+w, upgrade);
        }
        last = u;
        u = par[u];
    }
    if(maxCost >= 0){
        ans = max(ans, solve());
    }
    return ans;
}

• 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