# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1201270 | PagodePaiva | Closing Time (IOI23_closing) | C++20 | 0 ms | 0 KiB |
#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
vector <pair <int, int>> g[N];
int mark[N];
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-1;i++){
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
int ans = 0;
priority_queue <pair <int, int>> pq;
for(auto [v, w] : g[X]){
pq.push_back({-w, v});
}
for(auto [v, w] : g[Y]){
pq.push_back({-w, v});
}
int ans = 0, sum = 0;;
while(!pq.empty()){
auto [w, v] = pq.top();
pq.pop();
if(mark[v])
continue;
w *= -1;
if(sum+w > k){
return ans;
}
sum += w;
ans++;
mark[v] = 1;
for(auto [x, ww] : g[v]){
if(mark[x])
continue;
pq.push({-(ww+w), x});
}
}
return ans;
}