#include "closing.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 500 + 10;
const llong INF = 8e18;
const int INTINF = 2e9;
int n;
int x;
int y;
llong k;
int sz[MAXN];
int par[MAXN];
bool isOnPath[MAXN];
int suffixSizes[MAXN];
std::vector <int> path;
std::vector <int> pathSizes;
llong dpR[MAXN][2 * MAXN][2][2]; // root
llong dpC[MAXN][2 * MAXN][2][2]; // children, knapsack
llong dpS[MAXN][2 * MAXN][2][2]; // stick
bool blR[MAXN][2 * MAXN][2][2];
bool blC[MAXN][2 * MAXN][2][2];
bool blS[MAXN][2 * MAXN][2][2];
llong distX[MAXN];
llong distY[MAXN];
int child[2 * MAXN];
int dist[2 * MAXN];
int prev[2 * MAXN];
int eIDX[2 * MAXN];
int cnt;
void addEdge(int u, int v, int w)
{
child[cnt] = v;
dist[cnt] = w;
prev[cnt] = eIDX[u];
eIDX[u] = cnt;
cnt++;
}
void reset()
{
cnt = 0;
path.clear();
pathSizes.clear();
for (int i = 0 ; i < n ; ++i)
{
sz[i] = 0;
isOnPath[i] = false;
distX[i] = distY[i] = 0;
for (int j = 0 ; j <= 2 * n ; ++j)
{
for (int flagX = 0 ; flagX < 2 ; ++flagX)
{
for (int flagY = 0 ; flagY < 2 ; ++flagY)
{
dpR[i][j][flagX][flagY] = 0;
dpC[i][j][flagX][flagY] = 0;
dpS[i][j][flagX][flagY] = 0;
blR[i][j][flagX][flagY] = false;
blC[i][j][flagX][flagY] = false;
blS[i][j][flagX][flagY] = false;
}
}
}
}
}
void dfs(int node, int par, llong to[], llong dist)
{
to[node] = dist;
for (int idx = eIDX[node] ; idx != -1 ; idx = prev[idx])
{
if (par == child[idx])
{
continue;
}
dfs(child[idx], node, to, dist + child[idx]);
}
}
bool dfsPath(int node, int par)
{
if (node == y)
{
path.push_back(node);
return true;
}
for (int idx = eIDX[node] ; idx != -1 ; idx = prev[idx])
{
if (par == child[idx])
{
continue;
}
if (dfsPath(child[idx], node))
{
path.push_back(node);
return true;
}
}
return false;
}
void dfsSize(int node, int p)
{
sz[node] = 1;
par[node] = p;
for (int idx = eIDX[node] ; idx != -1 ; idx = prev[idx])
{
if (p == child[idx])
{
continue;
}
dfsSize(child[idx], node);
if (!isOnPath[child[idx]]) sz[node] += child[idx];
}
}
llong fRoot(int, int, int, int);
llong fChildren(int, int, int, int, int);
llong fStick(int, int, int, int);
llong fRoot(int node, int choose, int flagX, int flagY)
{
if (choose == 0)
{
return 0;
}
if (!flagX && !flagY)
{
return k + 1;
}
if (blR[node][choose][flagX][flagY])
{
return dpR[node][choose][flagX][flagY];
}
blR[node][choose][flagX][flagY] = true;
dpR[node][choose][flagX][flagY] = fChildren(node, eIDX[node], choose, flagX, flagY);
dpR[node][choose][flagX][flagY] = std::min(dpR[node][choose][flagX][flagY], k + 1);
return dpR[node][choose][flagX][flagY];
}
llong fChildren(int node, int idx, int choose, int flagX, int flagY)
{
if (idx == -1)
{
if (choose == 0) return 0;
return k + 1;
}
int current = child[idx];
if (blC[current][choose][flagX][flagY])
{
return dpC[current][choose][flagX][flagY];
}
blC[current][choose][flagX][flagY] = true;
if (isOnPath[current] || current == par[node])
{
return dpC[current][choose][flagX][flagY] = fChildren(node, prev[idx], choose, flagX, flagY);
}
dpC[current][choose][flagX][flagY] = k + 1;
for (int currX = 0 ; currX <= flagX ; ++currX)
{
for (int currY = 0 ; currY <= flagY ; ++currY)
{
for (int subtreeChoose = std::max(choose - 2 * suffixSizes[(prev[idx] == -1 ? n : child[prev[idx]])], currX + currY) ; subtreeChoose <= std::min(2 * sz[current], choose) ; ++subtreeChoose)
{
if (fChildren(node, prev[idx], choose - subtreeChoose, flagX, flagY) > k) continue;
dpC[current][choose][flagX][flagY] = std::min(dpC[current][choose][flagX][flagY], fChildren(node, prev[idx], choose - subtreeChoose, flagX, flagY) + std::max((currX == 0 ? 0 : distX[current]), (currY == 0 ? 0 : distY[current])) + fRoot(current, subtreeChoose - currX - currY, currX, currY));
}
}
}
return dpC[current][choose][flagX][flagY];
}
llong fStick(int idx, int choose, int flagX, int flagY)
{
if (idx == path.size())
{
if (choose == 0) return 0;
return k + 1;
}
if (blS[idx][choose][flagX][flagY])
{
return dpS[idx][choose][flagX][flagY];
}
blS[idx][choose][flagX][flagY] = true;
dpS[idx][choose][flagX][flagY] = k + 1;
for (int currX = 0 ; currX <= flagX ; ++currX)
{
for (int currY = flagY ; currY < 2 ; ++currY)
{
for (int subtreeChoose = std::max(choose - 2 * pathSizes[idx + 1], currX + currY) ; subtreeChoose <= std::min(2 * sz[path[idx]], choose) ; ++subtreeChoose)
{
if (fStick(idx + 1, choose - subtreeChoose, currX, currY) > k) continue;
dpS[idx][choose][flagX][flagY] = std::min(dpS[idx][choose][flagX][flagY], fStick(idx + 1, choose - subtreeChoose, currX, currY) + std::max((currX == 0 ? 0 : distX[path[idx]]), (currY == 0 ? 0 : distY[path[idx]])) + fRoot(path[idx], subtreeChoose - currX - currY, currX, currY));
}
}
}
return dpS[idx][choose][flagX][flagY];
}
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 = N;
x = X;
y = Y;
k = K;
std::fill(eIDX, eIDX + n, -1);
for (int i = 0 ; i < n - 1 ; ++i)
{
addEdge(U[i], V[i], W[i]);
addEdge(V[i], U[i], W[i]);
}
dfs(x, -1, distX, 0);
dfs(y, -1, distY, 0);
dfsPath(x, -1);
dfsSize(x, -1);
suffixSizes[n] = 0;
for (int i = 0 ; i < n ; ++i)
{
std::vector <int> children;
for (int idx = eIDX[i] ; idx != -1 ; idx = prev[idx])
{
children.push_back(idx);
}
std::reverse(children.begin(), children.end());
for (const int &idx : children)
{
int add = 0;
suffixSizes[child[idx]] = suffixSizes[(prev[idx] == -1 ? n : prev[idx])];
if (!isOnPath[child[idx]] && child[idx] != par[i])
{
add = sz[child[idx]];
}
suffixSizes[child[idx]] += add;
}
}
std::reverse(path.begin(), path.end());
for (const int &i : path)
{
isOnPath[i] = true;
}
pathSizes.resize(path.size() + 1, 0);
for (int i = path.size() - 1 ; i >= 0 ; --i)
{
pathSizes[i] = pathSizes[i + 1] + sz[path[i]];
}
for (int i = 2 * n ; i >= 1 ; --i)
{
if (fStick(0, i, 1, 0) <= k)
{
return i;
}
}
return 0;
}
Compilation message
closing.cpp: In function 'llong fStick(int, int, int, int)':
closing.cpp:198:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | if (idx == path.size())
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
1st lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
1525884 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 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 |
1 ms |
6492 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 |
1 ms |
6492 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 |
1 ms |
6488 KB |
1st lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
1st lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
1st lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
1st lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
1st lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
