Submission #1248824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248824		madamadam3	Closing Time (IOI23_closing)	C++20	0 / 100	64 ms	19524 KiB

closing

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

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;

struct Edge {
    int v, w;
};

int n, x, y;
ll k;
vi xi, yi, wi;
vector<vector<Edge>> adj;
const ll INF = 4e18;

int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
    n = N; x = X; y = Y; k = K; xi = U; yi = V; wi = W;
    adj.assign(n, vector<Edge>());
    for (int i = 0; i < n - 1; i++) {
        adj[xi[i]].push_back(Edge{yi[i], wi[i]});
        adj[yi[i]].push_back(Edge{xi[i], wi[i]});
    }

    int ans = 0;
    ll tl = 0;
    priority_queue<pair<ll, int>> xq, yq;
    xq.push({0, x}), yq.push({0, y});
    vector<bool> vis(n, false);

    while (tl <= k && !xq.empty() && !yq.empty()) {
        pair<ll, int> xc = xq.empty() ? make_pair(INF, -1) : xq.top();
        pair<ll, int> yc = yq.empty() ? make_pair(INF, -1) : yq.top();
        
        if (xc.first < yc.first) {
            vis[xc.second] = true;
            xq.pop();
            if (tl + xc.first > k) break;
            ans++;
            tl += xc.first;

            for (auto &e : adj[xc.second]) {
                if (vis[e.v]) continue;
                xq.push({xc.first + ll(e.w), e.v});
            }
        } else {
            vis[yc.second] = true;
            yq.pop();
            if (tl + yc.first > k) break;
            ans++;
            tl += yc.first;
            for (auto &e : adj[yc.second]) {
                if (vis[e.v]) continue;
                yq.push({yc.first + ll(e.w), e.v});
            }
        }
    }
    
    return ans;
}

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