Submission #840848

#	Time	Username	Problem	Language	Result	Execution time	Memory
840848		vjudge1	Closing Time (IOI23_closing)	C++17	30 / 100	1082 ms	32244 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);
        }
        sort(path.begin(), path.end(), [&](int i, int j) {
                return dX[i] < dX[j];
        });
        vector<int> both(N, 0);
        vector<int> chk;
        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);
                vector<int> vis(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;
                        queue<int> q;
                        for (int i : chk) {
                                cnt += 2;
                                q.emplace(i);
                                vis[i] = 1;
                        }
                        while (q.size()) {
                                int u = q.front();
                                q.pop();
                                for (auto [v, w] : adj[u]) {
                                        if (vis[v]) continue;
                                        if (c[v]) continue;
                                        if (dX[v] == dX[u] + w && dY[v] == dY[u] + w) {
                                                q.emplace(v);
                                                vis[v] = 1;
                                        }
                                }
                        }
                }
                priority_queue<pair<int64_t, int>> pq2, pq1;
                for (int i = 0; i < N; i++) {
                        if (both[i]) continue;
                        if (c[i]) continue;
                        if (vis[i]) {
                                pq2.emplace(-max(dX[i], dY[i]), i);
                        } else {
                                pq1.emplace(-min(dX[i], dY[i]), i);
                        }
                }
                vector<int> order;
                while (pq2.size()) {
                        auto [du, u] = pq2.top();
                        if (cost - du > K) break;
                        pq2.pop();
                        cost -= du;
                        order.emplace_back(u);
                        cnt += 2;
                }
                while (pq2.size()) pq1.emplace(-min(dX[pq2.top().second], dY[pq2.top().second]), pq2.top().second), pq2.pop();
                auto upd = [&]() {
                        while (pq1.size()) {
                                auto [du, u] = pq1.top();
                                if (cost - du > K) return;
                                pq1.pop();
                                cost -= du;
                                c[u] = 1;
                                cnt++;
                        }
                };
                upd();
                int ans = cnt;
                while (order.size()) {
                        cnt -= 2;
                        int u = order.back();
                        order.pop_back();
                        cost -= max(dX[u], dY[u]);
                        pq1.emplace(-min(dX[u], dY[u]), u);
                        upd();
                        ans = max(ans, cnt);
                }
                return ans;
        };

        int res = solve(0);
        for (int i = 0; i < path.size(); i++) {
                cur = 0;
                chk.clear();
                both = vector<int>(N, 0);
                for (int j = i; j < path.size(); j++) {
                        chk.emplace_back(path[j]);
                        cur += max(dX[path[j]], dY[path[j]]);
                        both[path[j]] = 1;
                        res = max(res, solve());
                }
        }
        return res;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int i = 0; i < path.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
closing.cpp:123:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                 for (int j = i; j < path.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~

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