This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> i2;
typedef tuple<ll, int, int, int> i4;
struct Cmp {
bool operator()(const i4& a, const i4& b) const {
return get<0>(a) > get<0>(b);
}
};
typedef priority_queue<i4, vector<i4>, Cmp> heap4;
int max_score(int N, int X, int Y, ll K,
vector<int> U, vector<int> V, vector<int> W) {
vector<vector<i2>> E(N);
for(int i = 0; i < N - 1; ++i) {
E[U[i]].push_back({V[i], W[i]});
E[V[i]].push_back({U[i], W[i]});
}
auto calc_dist = [&](int s) {
vector<ll> D(N, 0);
function<void(int, int)> rec;
rec = [&](int u, int p) {
for(const auto& [v, w] : E[u]) {
if(v != p) {
D[v] = D[u] + w;
rec(v, u);
}
}
};
rec(s, -1);
return D;
};
auto find_path = [&]() {
vector<int> path;
function<bool(int, int)> rec;
rec = [&](int u, int p) {
path.push_back(u);
if(u == Y) {
return true;
}
for(const auto& [v, _] : E[u]) {
if(v != p && rec(v, u)) {
return true;
}
}
path.pop_back();
return false;
};
rec(X, -1);
return path;
};
vector<vector<ll>> D = {calc_dist(X), calc_dist(Y)};
auto solve = [&](heap4& pq, ll k, bool cross) {
int s = 0;
while(!pq.empty()) {
auto [d, u, p, c] = pq.top(); pq.pop();
if(d > k) {
break;
}
s++;
k -= d;
for(auto [v, w]: E[u]) {
if(v != p) {
int b = -1;
// w > 0, so can't be equal
if(D[c][v] < D[1-c][v]) {
b = D[c][v];
} else if(cross) {
b = D[c][v] - D[1-c][v];
}
if(b != -1) {
pq.emplace(b, v, u, c);
}
}
}
}
return s;
};
int ans;
{
heap4 pq;
pq.emplace(0, X, -1, 0);
pq.emplace(0, Y, -1, 1);
ans = solve(pq, K, false);
}
{
ll k = K;
vector<int> P = find_path();
for(int j = 0; j < P.size(); ++j) {
k -= min(D[0][P[j]], D[1][P[j]]);
}
int i;
for(i = 0; i < P.size() && D[0][P[i]] < D[1][P[i]]; ++i) {}
i--;
heap4 pq;
for(auto [v, w]: E[X]) if(v != P[1]) pq.emplace(w, v, X, 0);
for(auto [v, w]: E[Y]) if(v != P[P.size()-2]) pq.emplace(w, v, Y, 1);
pq.emplace(D[0][P[i+1]] - D[1][P[i+1]], P[i+1], P[i], 0);
pq.emplace(D[1][P[i]] - D[0][P[i]], P[i], P[i+1], 1);
if(k >= 0) {
ans = max(ans, (int) P.size() + solve(pq, k, true));
}
}
return ans;
}
Compilation message (stderr)
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int j = 0; j < P.size(); ++j) {
| ~~^~~~~~~~~~
closing.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(i = 0; i < P.size() && D[0][P[i]] < D[1][P[i]]; ++i) {}
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |