Submission #843975

#	Time	Username	Problem	Language	Result	Execution time	Memory
843975		Lucpp	Closing Time (IOI23_closing)	C++17	26 / 100	100 ms	37056 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(){
    int n = (int)costs.size();
    vector<ll> dp(2*n+1, inf);
    dp[0] = 0;
    for(auto [c1, c2] : costs){
        for(int i = 2*n; i >= 0; i--){
            if(i > 0) dp[i] = min(dp[i], dp[i-1] + c1);
            if(i > 1) dp[i] = min(dp[i], dp[i-2] + c2);
        }
    }
    int score = 0;
    while(score < 2*n && dp[score+1] <= maxCost) score++;
    return score;
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
    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: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17