#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <cstdint>
#include <functional>
#include <numeric>
#include <limits>
using namespace std;
struct Graph {
protected:
vector<vector<pair<int, int64_t>>> edges;
vector<int64_t> low, high, distToX, distToY;
vector<int> path;
int N, X, Y;
int64_t K;
int64_t tempK;
int tempScore, score;
vector<bool> inOverlap, inLowHeap;
vector<int> inOutsideHeapCount;
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>> OverlapHeap;
stack<int> lowHeap;
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> OutsideHeap;
public:
Graph(int n, int x, int y, int64_t k) : N(n), X(x), Y(y), K(k), edges(n),
low(n), high(n), distToX(n), distToY(n), inOverlap(n, false),
inLowHeap(n, false), inOutsideHeapCount(n, 0), tempK(0), tempScore(0), score(-1) {}
void build_edge(int *u, int *v, int *w) {
for(int i = 0; i < N-1; i++){
addEdge(u[i], v[i], w[i]);
}
}
int findMaxScore() {
initialize();
if (!initLowHeap()) return score;
initOutsideHeap();
while (refreshScore());
return score;
}
protected:
void addEdge(int u, int v, int64_t w) {
edges[u].emplace_back(v, w);
edges[v].emplace_back(u, w);
}
vector<int64_t> bfs(int start) {
vector<int64_t> dist(N, numeric_limits<int64_t>::max());
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& [v, w] : edges[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q.push(v);
}
}
}
return dist;
}
void initialize() {
distToX = bfs(X);
distToY = bfs(Y);
for (int i = 0; i < N; ++i) {
low[i] = min(distToX[i], distToY[i]);
high[i] = max(distToX[i], distToY[i]);
}
findPath();
}
void findPath() {
vector<int> prev(N, -1);
queue<int> q;
q.push(X);
vector<bool> visited(N, false);
visited[X] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == Y) break;
for (auto& [v, w] : edges[u]) {
if (!visited[v]) {
visited[v] = true;
prev[v] = u;
q.push(v);
}
}
}
for (int at = Y; at != -1; at = prev[at]) {
path.push_back(at);
}
reverse(path.begin(), path.end());
}
bool initLowHeap() {
vector<int> lowSort(N);
iota(lowSort.begin(), lowSort.end(), 0);
sort(lowSort.begin(), lowSort.end(), [this](int a, int b) { return low[a] < low[b]; });
for (int node : path) {
inLowHeap[node] = true;
}
int64_t sumLows = 0;
int count = 0;
for (int idx : lowSort) {
if (sumLows + low[idx] > K) break;
sumLows += low[idx];
count++;
}
score = count;
tempK = tempScore = 0;
for (int node : path) {
tempK += low[node];
tempScore++;
}
if (tempK >= K) return false;
for (int i : lowSort) {
if (!inLowHeap[i] && tempK + low[i] <= K) {
lowHeap.push(i);
inLowHeap[i] = true;
tempK += low[i];
tempScore++;
}
}
return true;
}
void initOutsideHeap() {
for (int i = 0; i < N; ++i) {
inOutsideHeapCount[i] = 1;
if (inLowHeap[i]) {
OutsideHeap.push({high[i] - low[i], i});
} else {
OutsideHeap.push({high[i], i});
}
}
}
bool refreshScore() {
if (lowHeap.empty()) return false;
int u = lowHeap.top();
lowHeap.pop();
if (inOverlap[u]) {
OverlapHeap.push({high[u], u});
} else {
tempScore--;
tempK -= low[u];
inLowHeap[u] = false;
OutsideHeap.push({high[u], u});
inOutsideHeapCount[u]++;
}
while (!OutsideHeap.empty() && !OverlapHeap.empty()) {
auto [costs, s] = OutsideHeap.top();
auto [costt, t] = OverlapHeap.top();
if (costs < costt) {
tempK -= (costt - costs);
OutsideHeap.pop();
OverlapHeap.pop();
inOverlap[t] = false;
OutsideHeap.emplace(costt, t);
OverlapHeap.emplace(costs, s);
inOverlap[s] = true;
} else {
break;
}
}
while (!OutsideHeap.empty() && tempK + OutsideHeap.top().first <= K) {
auto [costs, s] = OutsideHeap.top();
tempK += costs;
OutsideHeap.pop();
OverlapHeap.push({costs, s});
inOverlap[s] = true;
}
score = max(score, tempScore);
return true;
}
};
Compilation message
closing.cpp: In constructor 'Graph::Graph(int, int, int, int64_t)':
closing.cpp:19:13: warning: 'Graph::K' will be initialized after [-Wreorder]
19 | int64_t K;
| ^
closing.cpp:15:40: warning: 'std::vector<std::vector<std::pair<int, long int> > > Graph::edges' [-Wreorder]
15 | vector<vector<pair<int, int64_t>>> edges;
| ^~~~~
closing.cpp:29:5: warning: when initialized here [-Wreorder]
29 | Graph(int n, int x, int y, int64_t k) : N(n), X(x), Y(y), K(k), edges(n),
| ^~~~~
closing.cpp:23:17: warning: 'Graph::inOutsideHeapCount' will be initialized after [-Wreorder]
23 | vector<int> inOutsideHeapCount;
| ^~~~~~~~~~~~~~~~~~
closing.cpp:20:13: warning: 'int64_t Graph::tempK' [-Wreorder]
20 | int64_t tempK;
| ^~~~~
closing.cpp:29:5: warning: when initialized here [-Wreorder]
29 | Graph(int n, int x, int y, int64_t k) : N(n), X(x), Y(y), K(k), edges(n),
| ^~~~~
/usr/bin/ld: /tmp/cc2QWpwc.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
