#include "closing.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
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 shouldBreak[MAXN];
llong applied[MAXN];
int atLeastX[MAXN];
int atLeastY[MAXN];
bool shouldSkip[MAXN];
bool reachableX[MAXN];
bool reachableY[MAXN];
int pos[MAXN];
struct Element
{
llong cost;
int type;
int node;
friend bool operator < (const Element &a, const Element &b)
{
if (a.cost != b.cost) return a.cost > b.cost;
if (a.type != b.type) return a.type > b.type;
return a.node < b.node;
}
};
std::priority_queue <Element> pq;
std::vector <int> path;
void reset()
{
while (!pq.empty())
{
pq.pop();
}
path.clear();
std::fill(distX, distX + n, 0);
std::fill(distY, distY + n, 0);
std::fill(reachableX, reachableX + n, 0);
std::fill(reachableY, reachableY + n, 0);
toX.clear(); toY.clear(); toBoth.clear();
for (int i = 0 ; i < n ; ++i)
{
applied[i] = 0;
atLeastX[i + 1] = 0;
atLeastY[i + 1] = 0;
pos[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);
resetBL();
dfsPath(x, 0);
for (int i = 0 ; i < path.size() ; ++i)
{
pos[path[i]] = i;
}
for (int i = 0 ; i < n ; ++i)
{
if (distX[i] <= distY[i])
{
pq.push({distX[i], 0, i});
pq.push({distY[i], 2, i});
} else
{
pq.push({distY[i], 1, i});
pq.push({distX[i], 2, i});
}
}
int res = 0;
while (!pq.empty())
{
auto [cost, type, node] = pq.top();
pq.pop();
bool neighGood = true;
if (!shouldSkip[node]) neighGood = false;
if (pos[node] > 0 && !reachableY[path[pos[node] - 1]]) neighGood = false;
if (pos[node] + 1 < path.size() && !reachableX[path[pos[node] + 1]]) neighGood = false;
if (type == 2 && neighGood && k >= cost - applied[node])
{
res++;
k -= cost - applied[node];
reachableX[node] = true;
reachableY[node] = true;
}
if (type != 2 && k >= cost)
{
res++;
k -= cost;
applied[node] = cost;
shouldSkip[node] = true;
if (type == 0) reachableX[node] = true;
if (type == 1) reachableY[node] = true;
}
}
return res;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:138:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int i = 0 ; i < path.size() ; ++i)
| ~~^~~~~~~~~~~~~
closing.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | if (pos[node] + 1 < path.size() && !reachableX[path[pos[node] + 1]]) neighGood = false;
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
36668 KB |
Output is correct |
| 2 |
Correct |
156 ms |
39996 KB |
Output is correct |
| 3 |
Correct |
76 ms |
15184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 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 |
2 ms |
12632 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 |
2 ms |
12632 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 |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 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 |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 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 |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 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 |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 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 |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
