#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<vector<pair<int, int>>> G;
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);
}
}
}
void dfs_find_par(int v, int p, vector<int> &par) {
par[v] = p;
for (auto i : G[v]) {
if (i.first != p) {
dfs_find_par(i.first, v, par);
}
}
}
void init(int n) {
G.clear();
ban.clear();;
G.resize(n);
ban.resize(n);
}
void dfs(int v, int par, long long d, vector<pair<long long, int>> &value, vector<int> &aboba, vector<int> &h) {
aboba[v] = 1;
value.emplace_back(d, v);
for (auto i : G[v]) {
if (i.first == par || ban[i.first])
continue;
h[i.first] = h[v] = 1;
dfs(i.first, v, d + i.second, value, aboba, h);
}
}
int solve(int n, int l, int r, long long k, vector<int> &path, vector<long long> &dist1,
vector<long long> &dist2, int x, int y) {
fill(all(ban), 0);
for (int i = l; i < r; ++i) {
ban[path[i]] = 1;
}
ban[x] = 1, ban[y] = 1;
vector<pair<long long, int>> value1;
vector<pair<long long, int>> value2;
vector<int> under_border(n);
vector<int> h(n);
if (!ban[path[1]])
dfs(path[1], -1, min(dist1[path[1]], dist2[path[1]]), value1, under_border, h);
if (!ban[path[path.size() - 2]])
dfs(path[path.size() - 2], -1, min(dist1[path[path.size() - 2]], dist2[path[path.size() - 2]]), value1, under_border, h);
long long sum = 0;
vector<pair<int, int>> ans; // добавить эти вершины в самом начале
int cnt = 0;
for (int i : path) {
if (ban[i] && i != x && i != y) {
if (l != r) {
cnt += 2;
ans.emplace_back(i, 2);
sum += max(dist1[i], dist2[i]);
}
} else if (i != x && i != y) {
if (l != r) {
cnt += 1;
ans.emplace_back(i, 1);
sum += min(dist1[i], dist2[i]);
}
}
}
for (int i : path)
ban[i] = 1;
// cout << sum << ' ' << k << '\n';
vector<int> used(n);
if (l != r) {
for (int i : path) {
if (i != x && i != y)
used[i] = 1;
}
}
if (sum > k)
return -1;
else
k -= sum;
int aboba = 0;
for (int i = l; i < r; ++i) {
dfs(path[i], -1, max(dist1[path[i]], dist2[path[i]]), value2, under_border, h);
}
fill(all(under_border), 0);
fill(all(h), 0);
h[x] = h[y] = 1;
dfs(x, -1, 0, value1, under_border, h);
dfs(y, -1, 0, value1, under_border, h);
for (int i = 0; i < (int) value1.size(); ++i) {
if (used[value1[i].second]) {
swap(value1[i], value1.back());
value1.pop_back();
--i;
}
}
for (int i = 0; i < (int) value2.size(); ++i) {
if (used[value2[i].second]) {
swap(value2[i], value2.back());
value2.pop_back();
--i;
}
}
sort(all(value1));
sort(all(value2));
vector<long long> cnt_under(value1.size() + 1);
vector<long long> sum_depth(value1.size() + 1);
vector<long long> pref1(value1.size() + 1);
vector<long long> pref2(value2.size() + 1);
for (int i = 0; i < (int) value1.size(); ++i) {
cnt_under[i + 1] = cnt_under[i] + under_border[value1[i].second];
}
for (int i = 0; i < (int) value1.size(); ++i) {
sum_depth[i + 1] = sum_depth[i] + sum_depth[value1[i].second];
}
for (int i = 0; i < (int) value1.size(); ++i) {
pref1[i + 1] = pref1[i] + value1[i].first;
}
for (int i = 0; i < (int) value2.size(); ++i) {
pref2[i + 1] = pref2[i] + value2[i].first;
}
for (int i1 = 0; i1 <= (int) value1.size(); ++i1) {
for (int i2 = 0; i2 <= (int) value2.size(); ++i2) {
long long ost = k - pref1[i1] - pref2[i2];
if (ost >= 0) {
int L = 0, R = cnt_under[i1] + 1;
while (R - L > 1) {
int mid = (L + R) / 2;
if (sum_depth[mid] * dist1[y] <= ost)
L = mid;
else
R = mid;
}
// int aboba_ost = max(cnt_under[i1], ost / dist1[y]);
aboba = max(aboba, L + cnt + i1 + 2 * i2);
} else {
break;
}
}
}
return aboba;
// for (int i = l; i < r; ++i) {
// dfs(path[i], -1, max(dist1[path[i]], dist2[path[i]]), value2);
// }
// sort(rall(value1));
// sort(rall(value2));
// // for (auto i : value1) {
// // cout << i.first << ' ' << i.second << '\n';
// // }
// while (value1.size() || value2.size()) {
// if (value1.size() && used[value1.back().second]) {
// value1.pop_back();
// continue;
// } else if (value2.size() && used[value2.back().second]) {
// value2.pop_back();
// continue;
// }
// // добавить used, чтобы вершина не бралась дважды + не брать на пути.
// if (!value1.size()) {
// if (value2.back().first > k) {
// break;
// } else {
// ans.emplace_back(value2.back().second, 2);
// k -= value2.back().first;
// used[value2.back().second] = 1;
// value2.pop_back();
// }
// } else if (!value2.size()) {
// if (value1.back().first > k) {
// break;
// } else {
// ans.emplace_back(value1.back().second, 1);
// k -= value1.back().first;
// used[value1.back().second] = 1;
// value1.pop_back();
// }
// } else {
// if (k >= value1.back().first && (k < value2.back().first ||
// (2 * value1.back().first < value2.back().first))) {
// // value1 оптимальнее
// ans.emplace_back(value1.back().second, 1);
// k -= value1.back().first;
// used[value1.back().second] = 1;
// value1.pop_back();
// } else if (k >= value2.back().first) {
// ans.emplace_back(value2.back().second, 2);
// k -= value2.back().first;
// used[value2.back().second] = 1;
// value2.pop_back();
// } else {
// break;
// }
// }
// }
// while (value2.size() && used[value2.back().second]) {
// value2.pop_back();
// }
// if (value2.size()) {
// for (int i = (int) ans.size() - 1; i >= 0; --i) {
// if (ans[i].second == 1) {
// if (k + min(dist1[ans[i].first], dist2[ans[i].first]) >= value2.back().first) {
// swap(ans[i], ans.back());
// ans.pop_back();
// ans.emplace_back(value2.back().second, 2);
// value2.pop_back();
// }
// break;
// }
// }
// }
// int cnt = 0;
// for (auto i : ans) {
// cnt += i.second;
// }
// return cnt;
}
int max_score(int n, int x, int y, long long k,
vector<int> u, vector<int> v, vector<int> w) {
init(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);
vector<int> path;
{
vector<int> par(n);
dfs_find_par(x, -1, par);
int tmp = y;
while (tmp != x) {
path.push_back(tmp);
tmp = par[tmp];
}
path.push_back(tmp);
}
// int ans = solve(n, -1, -1, k, path, dist1, dist2, x, y);
// for (int l = 0; l < (int) path.size(); ++l) {
// for (int r = l + 1; r <= (int) path.size(); ++r) {
// ans = max(ans, solve(n, l, r, k, path, dist1, dist2, x, y));
// // cout << l << ' ' << r << ' ' << solve(n, l, r, k, path, dist1, dist2, x, y) << '\n';
// }
// }
return solve(n, 1, path.size() - 1, k, path, dist1, dist2, x, y);
// return solve(n, 1, 3, k, path, dist1, dist2, x, y);
// return ans;
}
#ifdef LOCAL
int main()
{
// BEGIN SECRET
{
std::string in_secret = "cc61ad56a4797fb3f5c9529f73ce6fcedd85669b";
std::string out_secret = "081ce3c351cbf526b37954b9ad30f2b531a7585c";
char secret[1000];
assert(1 == scanf("%s", secret));
if (std::string(secret) != in_secret)
{
printf("%s\n", out_secret.c_str());
printf("SV\n");
fclose(stdout);
return 0;
}
}
// END SECRET
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> N(Q), X(Q), Y(Q);
std::vector<long long> K(Q);
std::vector<std::vector<int>> U(Q), V(Q), W(Q);
for (int q = 0; q < Q; q++)
{
assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
U[q].resize(N[q] - 1);
V[q].resize(N[q] - 1);
W[q].resize(N[q] - 1);
for (int i = 0; i < N[q] - 1; ++i)
{
assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
}
}
fclose(stdin);
std::vector<int> result(Q);
for (int q = 0; q < Q; q++)
{
result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
}
// BEGIN SECRET
{
std::string out_secret = "081ce3c351cbf526b37954b9ad30f2b531a7585c";
printf("%s\n", out_secret.c_str());
printf("OK\n");
}
// END SECRET
for (int q = 0; q < Q; q++)
{
printf("%d\n", result[q]);
}
fclose(stdout);
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
28856 KB |
1st lines differ - on the 1st token, expected: '451', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
