Submission #957345

#	Time	Username	Problem	Language	Result	Execution time	Memory
957345		jamesbamber	Closing Time (IOI23_closing)	C++17	83 / 100	1135 ms	1667392 KiB

closing

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

typedef long long ll;

vector<vector<pair<int,ll>>> ad;
vector<ll> on_path, dist, prv;
int n;

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

int greedy(ll k, int s1, int s2){
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> pq;
    pq.push({0, s1, -1}); pq.push({0, s2, -1});
    int ct = 0;
    while(pq.size()){
        auto [c, v, prv] = pq.top(); pq.pop();
        if(k-c < 0) return ct;
        k -= c; ct++;

        for(auto [u, w]: ad[v]){
            if(u == prv) continue;
            pq.push({c+w, u, v});
        }
    }
    return ct;
}

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

    dist.assign(n, 0); prv.assign(n, -1); on_path.assign(n, 0);

    dfs(X, -1);
    int curr = Y, path_sz = 0;
    while(curr != -1){
        on_path[curr] = 1; path_sz++;
        curr = prv[curr];
    }

    vector<ll> distX = dist;
    dist.assign(n, 0); dfs(Y, -1);
    vector<ll> distY = dist;

    int ans = greedy(K, X, Y);
    if(distX[Y] > K*2) return ans;

    vector dp(n+1, vector<ll>(2*n+1, 1e18+1));

    dp[0][path_sz] = 0;
    for(int i=0; i<n; i++){
        if(!on_path[i]) continue;
        dp[0][path_sz] += min(distX[i], distY[i]);
    }

    for(int i=0; i<n; i++){
        dp[i+1] = dp[i];
        if(!on_path[i]){
            ll d1 = min(distX[i], distY[i]), d2 = max(distX[i], distY[i]);
            for(int j=0; j<2*n; j++){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + d1);
                if(j+2 < 2*n+1) dp[i+1][j+2] = min(dp[i+1][j+2], dp[i][j] + d2);
            }
        }
        else{
            ll d = abs(distX[i] - distY[i]);
            for(int j=0; j<2*n; j++){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + d);
            }
        }
    }

    for(int i=0; i<2*n+1; i++){
        if(dp[n][i] <= K) ans = max(ans, i);
    }
    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: 0 / 17