Submission #1212026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212026		trimkus	Closing Time (IOI23_closing)	C++20	17 / 100	60 ms	18756 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < N - 1; ++i) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    vector<ll> c(N);
    ll sum = 0;
    int res = 0;
    priority_queue<array<ll, 3>> pq;
    vector<vector<bool>> vis(2, vector<bool>(N));
    pq.push({0, X, 0});
    pq.push({0, Y, 1});
    vis[0][X] = 1;
    vis[1][Y] = 1;
    while (pq.size()) {
        ll T =  -pq.top()[0];
        int v = pq.top()[1];
        int p = pq.top()[2];
        pq.pop();
        // cout << v << " , " << p << " = " << T << "\n";
        if (sum + T - c[v] > K) continue;
        res += 1;
        sum += T - c[v];
        c[v] = T;
        for (auto& [u, w] : adj[v]) {
            if (vis[p][u]) continue;
            vis[p][u] = 1;
            pq.push({-T - w, u, p});
        }
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 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