Submission #1226210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226210		mariaclara	Closing Time (IOI23_closing)	C++20	43 / 100	238 ms	32908 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second

vl calc_dist(int X, vector<vector<pii>> edges) {
    int N = sz(edges);
    vl dist(N, 1e12);
    vi vis(N);

    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0,X});
    dist[X] = 0;

    while(!pq.empty()) {
        auto [D,at] = pq.top();
        pq.pop();

        if(vis[at]) continue;
        vis[at] = 1;

        for(auto [viz, peso] : edges[at]) {
            if(dist[viz] > D + peso) {
                dist[viz] = D + peso;
                pq.push({D+peso, viz});
            }
        }
    }

    return dist;
}

int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
    vector<vector<pii>> edges(N);

    for(int i = 0; i+1 < N; i++)
        edges[U[i]].pb({V[i], W[i]}), edges[V[i]].pb({U[i], W[i]});

    vl distX = calc_dist(X, edges), distY = calc_dist(Y, edges);
    set<pli> cam;

    for(int i = 0; i < N; i++)
        cam.insert({min(distX[i], distY[i]), i});

    int ans1 = 0, ans2 = 0;
    ll at_val = 0;

    while(!cam.empty()) {
        auto [D, ind] = *cam.begin();
        cam.erase(cam.begin());

        at_val += D;
        if(at_val > K) break;
        ans1++;
    }

    cam.clear();
    vector<bool> vis(N);
    at_val = 0;

    for(int i = 0; i < N; i++) {
        if(distX[Y] == distX[i] + distY[i]) {
            at_val += min(distX[i], distY[i]);
            ans2++;
            vis[i] = 1;
            cam.insert({distX[Y] - 2*min(distX[i], distY[i]), i});
        }
        else cam.insert({min(distX[i], distY[i]), i});
    }

    if(at_val > K) ans2 = 0;

    while(!cam.empty() and at_val <= K) {
        auto [D, ind] = *cam.begin();
        cam.erase(cam.begin());

        if(!vis[ind]) {
            vis[ind] = 1;
            cam.insert({max(distX[ind], distY[ind]) - D, ind});
        }

        at_val += D;
        if(at_val > K) break;
        ans2++;
    }

    return max(ans1, ans2);
}

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