제출 #1248827

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

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;

struct Edge {
    int v, w;
};

int n, x, y;
ll k;
vi xi, yi, wi;
vector<vector<Edge>> adj;
const ll INF = 4e18;

int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
    n = N; x = X; y = Y; k = K; xi = U; yi = V; wi = W;
    adj.assign(n, vector<Edge>());
    for (int i = 0; i < n - 1; i++) {
        adj[xi[i]].push_back(Edge{yi[i], wi[i]});
        adj[yi[i]].push_back(Edge{xi[i], wi[i]});
    }

    int ans = 0;
    ll tl = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.push({0, x}), q.push({0, y});
    vector<bool> vis(n, false);

    while (tl <= k && !q.empty()) {
        auto cur = q.top(); q.pop();
        vis[cur.second] = true;

        if (tl + cur.first > k) break;
        tl += cur.first;
        ans++;

        for (auto &e : adj[cur.second]) {
            if (vis[e.v]) continue;
            q.push({cur.first + ll(e.w), e.v});
        }
    }
    
    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