#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3+5;
const long long INF = 1e18;
int onp[maxn];
long long depX[maxn], depY[maxn];
vector<pair<int, int>> g[maxn];
void dfsX(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depX[v.first] = depX[x] + v.second;
dfsX(v.first, x);
}
}
void dfsY(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depY[v.first] = depY[x] + v.second;
dfsY(v.first, x);
}
}
long long solve1(int n, long long k)
{
vector<long long> vec;
vec.insert(vec.end(), depX, depX + n);
vec.insert(vec.end(), depY, depY + n);
sort(vec.begin(), vec.end());
long long crr = 0;
for (int i = 0; i < vec.size(); i++)
{
crr += vec[i];
if (crr > k)
return i;
}
return vec.size();
}
vector<int> path;
bool dfs_path(int x, int endp, int p = -1)
{
if (x == endp)
return (onp[x] = true);
for (auto v : g[x])
{
if (v.first == p)
continue;
onp[x] |= dfs_path(v.first, endp, x);
}
return onp[x];
}
vector<long long> vec1, vec2;
vector<long long> knapsack[maxn];
long long dp[maxn][maxn];
void dfs_gen(int x, int p, long long cnst){
long long val;
if(p == -1)val = 0;
else val = min(depX[x],depY[x]);
if(val > cnst)vec2.push_back(val);
else vec1.push_back(val);
for(auto v: g[x]){
if(v.first == p || onp[v.first])continue;
dfs_gen(v.first, x, cnst);
}
}
long long solve2(int n, long long k, int x, int y)
{
dfs_path(x, y);
int len = 0;
for (int i = 0; i < n; i++)
{
if (onp[i])
{
k -= min(depX[i], depY[i]);
vec1.clear();
vec2.clear();
long long inc = abs(depX[i] - depY[i]);
dfs_gen(i, -1, inc);
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
knapsack[len] = vec1;
for(auto v: vec1)knapsack[len].push_back(inc);
for(auto v: vec2){
knapsack[len].push_back(v);
knapsack[len].push_back(inc);
}
for(int i = 1; i < knapsack[len].size(); i++)knapsack[len][i] += knapsack[len][i-1];
len++;
}
}
if (k < 0)
return 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++)dp[i][j] = INF;
}
dp[0][0] = 0;
for(int i = 0; i < len; i++){
for(int j = 0; j <= n; j++){
if(dp[i][j] == INF)continue;
dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
for(int k = 0; k < knapsack[i].size(); k++){
dp[i+1][j+k+1] = min(dp[i+1][j+k+1], dp[i][j] + knapsack[i][k]);
}
}
}
for(int i = n; i >= 0; i--){
if(dp[len][i] <= k)return i;
}
return 0;
}
void reset(int n)
{
for (int i = 0; i < n; i++)
{
g[i].clear();
onp[i] = 0;
}
path.clear();
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
reset(N);
for (int i = 0; i < N - 1; i++)
{
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
depX[X] = 0;
depY[Y] = 0;
dfsX(X);
dfsY(Y);
long long ans = max(solve1(N, K), solve2(N, K, X, Y));
return ans;
}
Compilation message
closing.cpp: In function 'long long int solve1(int, long long int)':
closing.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < vec.size(); i++)
| ~~^~~~~~~~~~~~
closing.cpp: In function 'long long int solve2(int, long long int, int, int)':
closing.cpp:99:22: warning: unused variable 'v' [-Wunused-variable]
99 | for(auto v: vec1)knapsack[len].push_back(inc);
| ^
closing.cpp:104:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 1; i < knapsack[len].size(); i++)knapsack[len][i] += knapsack[len][i-1];
| ~~^~~~~~~~~~~~~~~~~~~~~~
closing.cpp:118:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int k = 0; k < knapsack[i].size(); k++){
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
10188 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
