제출 #843973

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

closing

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

int N, X, Y;
ll maxCost;
vector<vector<pair<int, ll>>> g;

int solveGreedy(){
    priority_queue<tuple<ll, int, int>> pq;
    pq.emplace(0, X, X);
    pq.emplace(0, Y, Y);
    ll remain = maxCost;
    int score = 0;
    while(remain >= 0 && !pq.empty()){
        auto [c, u, p] = pq.top(); pq.pop();
        if(remain + c < 0) break;
        remain += c;
        score++;
        for(auto [v, w] : g[u]){
            if(v != p) pq.emplace(c-w, v, u);
        }
    }
    return score;
}

int max_score(int N_, int X_, int Y_, ll K, vector<int> U, vector<int> V, vector<int> W){
    N = N_, X = X_, Y = Y_, maxCost = K;
    g.clear();
    g.resize(N);
    for(int i = 0; i < N-1; i++){
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
    return solveGreedy();
}

• 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