#include <bits/stdc++.h>
using namespace std;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
const int n = N;
vector<vector<pair<int, int>>> tree(n);
for (int i = 0; i < n - 1; ++i) {
tree[V[i]].push_back({U[i], W[i]});
tree[U[i]].push_back({V[i], W[i]});
}
vector<int64_t> dx(n), dy(n);
auto dfs = [&] (auto&& self, int v, vector<int64_t>& dist, int p = -1, int64_t d = 0) -> void {
dist[v] = d;
for (auto [u, w] : tree[v]) {
if (u == p) continue;
self(self, u, dist, v, d + w);
}
};
dfs(dfs, X, dx);
dfs(dfs, Y, dy);
int64_t cost[n][4]={};
for (int i = 0; i < n; ++i) {
cost[i][0] = 0;
cost[i][1] = dx[i];
cost[i][2] = dy[i];
cost[i][3] = max(dx[i], dy[i]);
}
int64_t dp[n][2*n+1][4]={};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2*n+1; ++j) {
fill(dp[i][j], dp[i][j]+4, 1e18+1);
}
}
bool can_trans[4][4]={};
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
can_trans[i][j] = true;
}
}
dp[0][0][0] = 0;
dp[0][1][1] = cost[0][1];
dp[0][2][1] = cost[0][2];
dp[0][3][2] = cost[0][3];
for (int i = 1; i < n; ++i) {
if (i > X) {
can_trans[0][1] = false;
can_trans[0][3] = false;
}
if (i > Y) {
can_trans[0][2] = false;
can_trans[0][3] = false;
}
for (int j = 0; j < 2*n+1; ++j) {
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0]);
if (i > X)
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][1]);
if (i > Y)
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][2]);
if (i > Y)
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][3]);
if (can_trans[0][1] && j>0)
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][0] + cost[i][1]);
if (can_trans[0][2] && j>0)
dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][0] + cost[i][2]);
if (j>0) {
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][1] + cost[i][1]);
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][3] + cost[i][1]);
dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][2] + cost[i][2]);
dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][3] + cost[i][2]);
}
if (can_trans[0][3] && j>1) {
dp[i][j][3] = min(dp[i][j][3], dp[i-1][j-2][0] + cost[i][3]);
}
if (i <= Y && i >= X && j>1) {
dp[i][j][3] = min(dp[i][j][3], dp[i-1][j-2][1] + cost[i][3]);
}
}
}
for (int i = 2*n; i >= 0; --i) {
if (*min_element(dp[n-1][i], dp[n-1][i]+4) <= K) return i;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
876 ms |
2097152 KB |
Execution killed with signal 9 |
| 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: '4' |
| 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: '4' |
| 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: '4' |
| 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: '5' |
| 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: '5' |
| 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: '5' |
| 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: '5' |
| 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: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
