#include "closing.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 8e18;
const int INTINF = 2e9;
int n;
int x;
int y;
llong k;
llong distX[MAXN];
llong distY[MAXN];
std::vector <std::pair <llong,int>> toX;
std::vector <std::pair <llong,int>> toY;
std::vector <std::pair <llong,int>> toBoth;
std::vector <std::pair <int,int>> g[MAXN];
bool shouldSkip[MAXN];
bool shouldBreak[MAXN];
int atLeastX[MAXN];
int atLeastY[MAXN];
int posX[MAXN];
int posY[MAXN];
std::vector <int> path;
void reset()
{
path.clear();
std::fill(distX, distX + n, 0);
std::fill(distY, distY + n, 0);
toX.clear(); toY.clear(); toBoth.clear();
for (int i = 0 ; i < n ; ++i)
{
atLeastX[i + 1] = 0;
atLeastY[i + 1] = 0;
posX[i] = 0;
posY[i] = 0;
g[i].clear();
}
}
void resetBL()
{
std::fill(shouldSkip, shouldSkip + n, false);
std::fill(shouldBreak, shouldBreak + n, false);
}
void dfs(int node, int par, llong to[], llong dist)
{
to[node] = dist;
for (const auto &[u, d] : g[node])
{
if (u == par)
{
continue;
}
dfs(u, node, to, dist + d);
}
}
bool dfsPath(int node, int par)
{
if (node == y)
{
path.push_back(node);
return true;
}
for (const auto &[u, d] : g[node])
{
if (u == par)
{
continue;
}
if (dfsPath(u, node))
{
path.push_back(node);
return true;
}
}
return false;
}
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;
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]});
}
dfs(x, 0, distX, 0);
dfs(y, 0, distY, 0);
for (int i = 0 ; i < n ; ++i)
{
toX.push_back({distX[i], i});
toY.push_back({distY[i], i});
toBoth.push_back({std::max(distX[i], distY[i]), i});
}
std::sort(toX.begin(), toX.end());
std::sort(toY.begin(), toY.end());
std::sort(toBoth.begin(), toBoth.end());
for (int i = 0 ; i < n ; ++i)
{
posX[toX[i].second] = i;
posY[toY[i].second] = i;
}
dfsPath(x, 0);
// std::cout << "path\n";
// for (const auto &node : path)
// {
// std::cout << node << ' ';
// }
// std::cout << '\n';
int ptr = path.size() - 1;
for (int i = n - 1 ; i > 0 ; --i)
{
atLeastX[i] = atLeastX[i + 1];
if (ptr >= 0 && path[ptr] == toBoth[i].second)
{
atLeastX[i] = std::max(atLeastX[i], posX[toBoth[i].second] + 1);
ptr--;
}
}
ptr = path.size() - 1;
std::reverse(path.begin(), path.end());
for (int i = n - 1 ; i > 0 ; --i)
{
atLeastY[i] = atLeastY[i + 1];
if (ptr >= 0 && path[ptr] == toBoth[i].second)
{
atLeastY[i] = std::max(atLeastY[i], posY[toBoth[i].second] + 1);
ptr--;
}
}
// std::cout << "both\n";
// for (const auto &[dist, node] : toBoth)
// {
// std::cout << node << ' ' << dist << '\n';
// }
// std::cout << "x\n";
// for (const auto &[dist, node] : toX)
// {
// std::cout << node << ' ' << dist << '\n';
// }
// std::cout << "y\n";
// for (const auto &[dist, node] : toY)
// {
// std::cout << node << ' ' << dist << '\n';
// }
// std::cout << "at leasts\n";
// for (int i = 1 ; i <= n ; ++i)
// {
// std::cout << i << ": " << atLeastX[i] << ' ' << atLeastY[i] << '\n';
// }
int ans = 0;
for (int inBoth = 0 ; inBoth <= n ; ++inBoth)
{
for (int inX = atLeastX[inBoth] ; inX <= n ; ++inX)
{
for (int inY = atLeastY[inBoth] ; inY <= n ; ++inY)
{
resetBL();
int res = 0;
llong cost = 0;
for (int i = 0 ; i < inBoth ; ++i)
{
res += 2;
cost += toBoth[i].first;
shouldSkip[toBoth[i].second] = true;
}
for (int i = 0 ; i < inX ; ++i)
{
if (shouldSkip[toX[i].second])
{
continue;
}
res++;
cost += toX[i].first;
shouldBreak[toX[i].second] = true;
}
for (int i = 0 ; i < inY ; ++i)
{
if (shouldSkip[toY[i].second])
{
continue;
}
if (shouldSkip[toY[i].second])
{
cost = k + 1;
break;
}
res++;
cost += toY[i].first;
}
if (cost <= k)
{
ans = std::max(ans, res);
}
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1022 ms |
42508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 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 |
3 ms |
10584 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 |
3 ms |
10584 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 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
