제출 #1080436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080436		ArthuroWich	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	64 ms	22948 KiB

closing

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

int max_score(int n, int X, int Y, long long k, vector<int> U, vector<int> V, vector<int> W) {
    int ans = 0;
    vector<vector<pair<int, int>>> adj(n+1);
    vector<int> vis(n), distx(n, -1), disty(n, -1);
    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]});
    }
    set<tuple<int, int, int>> pq; // let 0 be x, 1 be y
    distx[X] = 0;
    disty[Y] = 0;
    pq.insert({0, X, 0});
    pq.insert({0, Y, 1});
    while(!pq.empty()) {
        auto [d, a, ind] = *pq.begin();
        pq.erase(*pq.begin());
        if (vis[a] == 0 && distx[a] != -1 && disty[a] != -1) {
            if (ind == 0) {
                pq.erase({disty[a], a, 1});
                pq.insert({disty[a]-distx[a], a, 1});
            } else {
                pq.erase({distx[a], a, 0});
                pq.insert({distx[a]-disty[a], a, 1});
            }
        }
        vis[a] = d;
        if (k < d) {
            break;
        } else {
            k -= d;
            ans++;
        }
        if (ind == 0) {
            for (auto [b, w] : adj[a]) {
                if (distx[b] != -1) {
                    continue;
                }
                distx[b] = distx[a]+w;
                if (vis[b] >= distx[b]) {
                    pq.insert({0, b, 0});
                } else {
                    pq.insert({(distx[b]-vis[b]), b, 0});
                }
            }
        } else {
            for (auto [b, w] : adj[a]) {
                if (disty[b] != -1) {
                    continue;
                }
                disty[b] = disty[a]+w;
                if (vis[b] >= disty[b]) {
                    pq.insert({0, b, 1});
                } else {
                    pq.insert({(disty[b]-vis[b]), b, 1});
                }
            }
        }
    }
    return ans;
}

• 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