제출 #1240937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240937		bangan	봉쇄 시간 (IOI23_closing)	C++20	8 / 100	68 ms	23108 KiB

closing

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

#define pb push_back
#define eb emplace_back
#define ALL(a) a.begin(), a.end()

#define ll long long
#define MP make_pair
#define MT make_tuple
#define pii pair<int, int>
#define Info tuple<ll, int, int>

const ll INF = 1ll << 50;

int none(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<vector<pii>> adj(N);
    for (int i=0; i < N-1; i++) {
        adj[V[i]].eb(U[i], W[i]);
        adj[U[i]].eb(V[i], W[i]);
    }

    vector<array<bool, 2>> done(N);
    vector<array<ll, 2>> d(N, {INF, INF});
    d[X][0] = 0;
    d[Y][1] = 0;
    priority_queue<Info, vector<Info>, greater<Info>> pq;
    pq.emplace(0, X, 0);
    pq.emplace(0, Y, 1);
    int ans = 0;

    while (!pq.empty()) {
        auto [_, v, s] = pq.top();
        cerr << "(v, s) = " << v << ' ' << s << endl;
        pq.pop();
        if (done[v][s]) continue;
        done[v][s] = true;
        if (d[v][s] <= K) ans++, K -= d[v][s];
        else break;
        
        for (auto [u, w] : adj[v]) {
            ll new_d = d[v][s]+w;
            if (done[u][s^1]) new_d = max(new_d - d[u][s^1], 0ll);
            if (new_d < d[u][s]) {
                d[u][s] = new_d;
                pq.push(MT(d[u][s], u, s));
            }
        }

        // auto [_, v] = pq.top();
        // pq.pop();
        // if (done[v]) continue;
        // done[v] = true;
        // if (d[v] <= K) {
        //     ans++;
        //     K -= d[v];
        // }
        // for (auto [u, w] : adj[v]) if (d[v]+w < d[u]) {
        //     d[u] = d[v]+w;
        //     pq.push(MP(d[u], u));
        // }
    }
    return ans;
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    return none(N, X, Y, K, U, V, W);
}

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