#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 1;
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w)
{
x++;
y++;
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < n - 1; ++i)
{
u[i]++;
v[i]++;
g[u[i]].push_back({v[i], w[i]});
g[v[i]].push_back({u[i], w[i]});
}
vector<vector<ll>> cost(n + 1, vector<ll>(2));
function<void(int, int, int)> compute_cost = [&](int node, int parent, int qui)
{
for (auto i : g[node])
{
if (i.first != parent)
{
cost[i.first][qui] = cost[node][qui] + i.second;
compute_cost(i.first, node, qui);
}
}
};
compute_cost(x, 0, 0);
compute_cost(y, 0, 1);
function<int()> greedy = [&]()
{
set<tuple<ll, int, int>> accesibile;
vector<vector<int>> viz(n + 1, vector<int>(2));
accesibile.insert({0, x, 0});
accesibile.insert({0, y, 1});
int ans = 0;
ll left = k;
while (!accesibile.empty())
{
int adam, qui, byqui;
tie(adam, qui, byqui) = *accesibile.begin();
accesibile.erase(accesibile.begin());
if (adam > left)
{
break;
}
left -= adam;
ans++;
viz[qui][byqui] = true;
for (auto i : g[qui])
{
if (!viz[i.first][byqui])
{
accesibile.insert({cost[i.first][byqui], i.first, byqui});
}
}
}
return ans;
};
function<int(int)> solve_root = [&](int root)
{
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + n + 1, vector<ll>(3, inf)));
vector<bool> important(n + 1);
vector<int> sz(n + 1);
function<void(int, int)> dfs_important = [&](int node, int parent)
{
if (node == x || node == y)
{
important[node] = true;
}
for (auto i : g[node])
{
if (i.first != parent)
{
dfs_important(i.first, node);
}
}
for (auto i : g[node])
{
if (i.first != parent)
{
important[node] = important[node] || important[i.first];
}
}
};
dfs_important(root, 0);
vector<ll> merged(n + n + 1, inf);
function<void(int, int)> dfs = [&](int node, int parent)
{
dp[node][1][0] = cost[node][0];
dp[node][1][1] = cost[node][1];
dp[node][2][2] = max(cost[node][0], cost[node][1]);
sz[node] = 1;
if (node == x)
{
dp[node][1][1] = inf;
}
if (node == y)
{
dp[node][1][0] = inf;
}
for (auto i : g[node])
{
if (i.first != parent)
{
dfs(i.first, node);
int maxleft = sz[node] + sz[node];
int maxright = sz[i.first] + sz[i.first];
for (int i = 0; i <= maxleft + maxright; ++i)
{
merged[i] = inf;
}
for (int color = 0; color <= 2; ++color)
{
for (int color2 = 0; color2 <= 2; ++color2)
{
if (color != color2 && color != 2)
{
continue;
}
for (int cntleft = 1; cntleft <= maxleft; ++cntleft)
{
if (dp[node][cntleft][color] > k)
{
continue;
}
for (int cntright = 1; cntright <= maxright; ++cntright)
{
merged[cntleft + cntright] = min(merged[cntleft + cntright], dp[node][cntleft][color] + dp[i.first][cntright][color2]);
}
}
}
for (int cnt = 1; cnt <= maxleft + maxright; ++cnt)
{
if (important[i.first])
{
dp[node][cnt][color] = merged[cnt];
}
else
{
dp[node][cnt][color] = min(dp[node][cnt][color], merged[cnt]);
}
}
}
sz[node] += sz[i.first];
}
}
};
dfs(root, 0);
for (int i = n + n; i >= 1; --i)
{
if (dp[root][i][2] <= k)
{
return i;
}
}
return 0;
};
int ans = greedy();
ll mini = inf;
int qui = 1;
for (int i = 1; i <= n; ++i)
{
ll val = abs(cost[i][0] - cost[i][1]);
if (val < mini)
{
mini = val;
qui = i;
}
}
ans = max(ans, solve_root(qui));
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
1556024 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '29' |
| 4 |
Halted |
0 ms |
0 KB |
- |
