Submission #840767

#	Time	Username	Problem	Language	Result	Execution time	Memory
840767		vjudge1	Closing Time (IOI23_closing)	C++17	43 / 100	704 ms	40160 KiB

closing

#include "closing.h"

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

vector<pair<int, int>> adj[200000];

void dfs(int u, int p, vector<int64_t>& d) {
        for (auto [v, c] : adj[u]) {
                if (v == p) continue;
                d[v] = d[u] + c;
                dfs(v, u, d);
        }
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
        for (int i = 0; i < N; i++) adj[i].clear();
        for (int i = 0; i < N - 1; i++) {
                adj[U[i]].emplace_back(V[i], W[i]);
                adj[V[i]].emplace_back(U[i], W[i]);
        }
        vector<int64_t> dX(N), dY(N);
        dfs(X, -1, dX);
        dfs(Y, -1, dY);
        vector<int> ord(N);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return max(dX[i], dY[i]) < max(dX[j], dY[j]);
        });
        vector<int> path;
        for (int i = 0; i < N; i++) {
                if (dX[i] + dY[i] == dX[Y]) path.emplace_back(i);
        }
        vector<int> both(N, 0);
        int64_t cur = 0;

        auto solve = [&](bool con = 1) {
                if (cur > K) return -N * 2;
                int cnt = 0;
                int64_t cost = cur;
                vector<int> c(N, 0);
                if (con) {
                        for (int x : path) {
                                if (both[x]) continue;
                                cost += min(dX[x], dY[x]);
                                c[x] = 1;
                                cnt++;
                        }
                        if (cost > K) return -N * 2;
                }
                priority_queue<pair<int64_t, int>> pq;
                for (int i = 0; i < N; i++) {
                        if (both[i]) continue;
                        if (c[i]) continue;
                        pq.emplace(-dX[i], i);
                        pq.emplace(-dY[i], i);
                }
                while (pq.size()) {
                        auto [v, i] = pq.top();
                        pq.pop();
                        if (c[i]) continue;
                        if (cost - v > K) break;
                        cnt++;
                        cost -= v;
                        c[i] = 1;
                }
                return cnt;
        };

        int res = solve(0);
        for (int i = 0; i < N; i++) {
                both[ord[i]] = 1;
                cur += max(dX[ord[i]], dY[ord[i]]);
                res = max(res, solve() + i * 2 + 2);
        }
        return res;
}

• 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