#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;
ll n, x, y, k;
vector<ll> u, v, w;
vector<vector<pair<ll,ll>>> g;
vector<ll> dist;
void dfs(ll ve, ll d = 0, ll p = -1) {
dist[ve] = min(dist[ve], d);
for (auto [uv, le] : g[ve]) {
if (uv == p)
continue;
dfs(uv, d + le, ve);
}
}
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;
k = K;
u.resize(N);
v.resize(N);
w.resize(N);
g.resize(N);
for (int i = 0; i < n - 1; i++) {
u[i] = U[i];
v[i] = V[i];
w[i] = W[i];
g[v[i]].push_back({u[i], w[i]});
g[u[i]].push_back({v[i], w[i]});
}
dist.assign(n, inf);
dfs(x);
dfs(y);
sort(dist.begin(), dist.end());
int cnt = 0;
for (int i = 0; i < n; i++) {
if (dist[i] <= k) {
cnt++;
k -= dist[i];
}
}
return cnt;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |