#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<pair<int, int>>> G;
const long long inf = 1'000'000'000'000'000'228ll;
vector<int> ban;
void dfs_calc_dist(int v, int par, long long d, vector<long long> &dist) {
dist[v] = d;
for (auto i : G[v]) {
if (i.first != par) {
dfs_calc_dist(i.first, v, d + i.second, dist);
}
}
}
bool dfs(int v, int par, long long d, long long &sum, vector<pair<long long, int>> &val, int &cnt) {
bool find_ban = false;
if (ban[v])
find_ban = true;
for (auto i : G[v]) {
if (i.first != par) {
if (dfs(i.first, v, d + i.second, sum, val, cnt)) {
find_ban = true;
}
}
}
if (find_ban) {
++cnt;
if (!ban[v]) {
sum += d;
}
} else {
val.emplace_back(d, v);
}
return find_ban;
}
int max_score(int n, int x, int y, long long k,
vector<int> u, vector<int> v, vector<int> w) {
G.clear();
G.resize(n);
ban.clear();
ban.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]);
}
vector<long long> dist1(n), dist2(n);
dfs_calc_dist(x, -1, 0, dist1);
dfs_calc_dist(y, -1, 0, dist2);
array<long long, 3> min_vertex = {inf, inf, -1};
for (int i = 0; i < n; ++i) {
min_vertex = min(min_vertex, array<long long, 3> {abs(dist1[i] - dist2[i]), dist1[i], i});
}
int V = min_vertex[2];
vector<long long> dist3(n);
dfs_calc_dist(V, -1, 0, dist3);
vector<pair<long long, int>> value;
for (int i = 0; i < n; ++i) {
value.emplace_back(dist3[i], i);
}
sort(all(value));
long long cur_sum_value = 0;
int ans = 0;
for (int i = 0; i <= n; ++i) {
vector<pair<long long, int>> val;
long long sum = 0;
int cnt = 0;
dfs(x, -1, 0, sum, val, cnt);
dfs(y, -1, 0, sum, val, cnt);
vector<int> used(n);
sort(all(val));
if (sum + cur_sum_value < k) {
int cur_get = 0;
for (auto j : val) {
if (used[j.second])
continue;
if (j.first + sum + cur_sum_value <= k) {
++cur_get;
sum += j.first;
ans = max(ans, cnt + cur_get);
}
}
} else {
break;
}
if (i != n) {
ban[value[i].second] = 1;
cur_sum_value += max(dist1[value[i].second], dist2[value[i].second]);
}
}
return ans;
}
#ifdef LOCAL
int main() {
int Q;
cin >> Q;
for (int i = 0; i < Q; ++i) {
int n, x, y;
long long k;
cin >> n >> x >> y >> k;
vector<int> u(n - 1), v(n - 1), w(n - 1);
for (int j = 0; j < n - 1; ++j) {
int a, b, c;
cin >> a >> b >> c;
u[j] = a, v[j] = b, w[j] = c;
}
cout << max_score(n, x, y, k, u, v, w) << '\n';
}
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
231 ms |
49972 KB |
Output is correct |
| 2 |
Correct |
231 ms |
51068 KB |
Output is correct |
| 3 |
Correct |
112 ms |
5204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
432 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 6 |
Halted |
0 ms |
0 KB |
- |
