# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1243606 | AlperenT_ | Closing Time (IOI23_closing) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200005;
vector<pair<int, int>> adj[MAXN];
ll K;
int N, X, Y;
vector<ll> dist(int src) {
vector<ll> d(N, -1);
queue<int> q;
q.push(src);
d[src] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto [v, w] : adj[u]) {
if (d[v] == -1) {
d[v] = d[u] + w;
q.push(v);
}
}
}
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> X >> Y >> K;
X--; Y--; // 0-indexed
for (int i = 0; i < N - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
u--; v--;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
auto dx = dist(X);
auto dy = dist(Y);
vector<pair<ll, ll>> nodes; // {min, max}
for (int i = 0; i < N; ++i) {
ll mn = min(dx[i], dy[i]);
ll mx = max(dx[i], dy[i]);
nodes.emplace_back(mn, mx);
}
// sort by min first
sort(nodes.begin(), nodes.end());
ll score = 0;
ll used = 0;
priority_queue<ll> upgrade;
for (auto [mn, mx] : nodes) {
if (used + mn <= K) {
used += mn;
score++;
upgrade.push(mx - mn); // possible upgrade to 2
} else {
break;
}
}
while (!upgrade.empty()) {
ll cost = upgrade.top(); upgrade.pop();
if (used + cost <= K) {
used += cost;
score++;
}
}
cout << score << '\n';
}