제출 #941227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941227		Trisanu_Das	봉쇄 시간 (IOI23_closing)	C++17	75 / 100	1129 ms	1413420 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);
        auto tmp = dX;
        tmp.insert(tmp.end(), dY.begin(), dY.end());
        sort(tmp.begin(), tmp.end());
        int ans = 0;
        int64_t sum = 0;
        for (int i = 0; i < N * 2; i++) {
                if (sum + tmp[i] > K) break;
                ans++;
                sum += tmp[i];
        }
        vector<int> op(N, 0);
        for (int i = 0; i < N; i++) op[i] = dX[i] + dY[i] == dX[Y];
        vector<vector<int64_t>> f(N + 1, vector<int64_t>(N * 2 + 1, 1e18 + 10));
        f[0][0] = 0;
        for (int i = 0; i < N; i++) {
                for (int j = 0; j <= N * 2; j++) {
                        if (f[i][j] > K) continue;
                        if (!op[i]) f[i + 1][j] = min(f[i][j], f[i + 1][j]);
                        if (f[i][j] + min(dX[i], dY[i]) > K) continue;
                        f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + min(dX[i], dY[i]));
                        if (f[i][j] + max(dX[i], dY[i]) > K) continue;
                        f[i + 1][j + 2] = min(f[i + 1][j + 2], f[i][j] + max(dX[i], dY[i]));
                }
        }
        int res = 0;
        for (int i = 0; i <= 2 * N; i++) if (f[N][i] <= K) res = i;
        return max(ans, res);
}

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