#include "closing.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int max_score(int n, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W) {
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
vector<vector<i64>> dis(n, vector<i64>(2, 0));
vector<vector<int>> next(n, vector<int>(2, -1));
function<void(int, int, int)> dfs = [&](int u, int p, int t) {
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dis[v][t] = dis[u][t] + w;
next[v][!t] = u;
dfs(v, u, t);
}
};
dfs(x, -1, 0);
dfs(y, -1, 1);
vector<int> path, onPath(n, 0);
int z = x;
while (true) {
path.push_back(z);
onPath[z] = 1;
if (z == y) {
break;
}
z = next[z][0];
}
vector<i64> one(n), two(n), upgCost(n);
for (int u = 0; u < n; ++u) {
one[u] = min(dis[u][0], dis[u][1]);
two[u] = max(dis[u][0], dis[u][1]);
upgCost[u] = two[u] - one[u];
}
vector<int> used(n, 0);
auto work = [&](bool mark, i64 k) {
int ret = 0;
vector<bool> vis(n, 0);
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
pq.push({0, x});
pq.push({0, y});
while (pq.size()) {
auto [cost, u] = pq.top();
pq.pop();
if (cost > k) {
break;
}
if (vis[u]) {
continue;
}
vis[u] = 1;
k -= cost;
++ret;
for (auto [v, w] : adj[u]) {
pq.push({one[v], v});
}
}
return ret;
};
int ans1 = work(0, k);
int ans2 = 0;
set<pair<i64, int>> upgrade;
set<pair<i64, int>> take;
set<pair<i64, int>> average;
for (auto u : path) {
k -= one[u];
++ans2;
upgrade.insert({upgCost[u], u});
}
if (k < 0) {
return ans1;
}
for (int u = 0; u < n; ++u) {
if (onPath[u]) continue;
take.insert({one[u], u});
average.insert({two[u], u});
}
int last = -1;
while (ans2 < 2 * n) {
i64 mn = 1e18, type = 0;
if (take.size()) {
mn = take.begin() -> first;
type = 1;
}
if (upgrade.size()) {
if (upgrade.begin() -> first < mn) {
type = 2;
}
mn = min(mn, upgrade.begin() -> first);
}
if (average.size()) {
if ((average.begin() -> first + 1) / 2 <= mn && average.begin() -> first <= k) {
type = 3;
}
}
if (mn > k && type != 3) {
break;
}
if (type == 1) {
auto [cost, u] = *take.begin();
k -= cost;
average.erase({two[u], u});
take.erase(take.begin());
upgrade.insert({upgCost[u], u});
++ans2;
last = cost;
} else if (type == 2) {
auto [cost, u] = *upgrade.begin();
k -= cost;
upgrade.erase(upgrade.begin());
++ans2;
last = cost;
} else if (type == 3) {
auto [cost, u] = *average.begin();
k -= cost;
take.erase({one[u], u});
average.erase(average.begin());
ans2 += 2;
}
}
if (average.size() && k + last >= average.begin() -> first) {
++ans2;
}
return max(ans1, ans2);
}
Compilation message
/usr/bin/ld: /tmp/ccfSRRmQ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNLZ0BR.o:closing.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
