#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
using ll = long long;
constexpr ll inf = 2e18;
ll maxCost;
vector<vector<pair<int, ll>>> g;
int solveGreedy(int X, int Y){
priority_queue<tuple<ll, int, int>> pq;
pq.emplace(0, X, X);
pq.emplace(0, Y, Y);
ll remain = maxCost;
int score = 0;
while(remain >= 0 && !pq.empty()){
auto [c, u, p] = pq.top(); pq.pop();
if(remain + c < 0) break;
remain += c;
score++;
for(auto [v, w] : g[u]){
if(v != p) pq.emplace(c-w, v, u);
}
}
return score;
}
vector<int> par;
vector<ll> dist;
vector<pair<ll, ll>> costs;
void dfs(int u){
for(auto [v, w] : g[u]){
if(v == par[u]) continue;
par[v] = u;
dist[v] = dist[u]+w;
dfs(v);
}
}
void collect(int u, ll myDist, ll upgrade){
costs.emplace_back(myDist, myDist+upgrade);
for(auto [v, w] : g[u]){
if(v == par[u]) continue;
collect(v, myDist+w, upgrade);
}
}
int solve(){
vector<ll> sing;
vector<pair<ll, ll>> doub;
for(auto [c1, c2] : costs){
if(c1 <= c2) sing.push_back(c1), sing.push_back(c2);
else doub.emplace_back(c1, c2);
}
sort(sing.begin(), sing.end());
sort(doub.begin(), doub.end(), [](pair<ll, ll> p, pair<ll, ll> q){return p.second < q.second;});
int p = (int)sing.size() - 1;
ll s = accumulate(sing.begin(), sing.end(), 0ll);
int ans = 0;
auto upd = [&](int cnt, ll x){
if(x > maxCost) return;
while(s+x > maxCost){
s -= sing[p--];
}
ans = max(ans, p + 1 + cnt);
};
upd(0, 0);
int n = (int)doub.size();
multiset<ll> add, sub;
for(auto [c1, c2] : doub) add.insert(c1);
ll co = 0;
for(int i = 0; i < n; i++){
ll y = co + *add.begin();
co += doub[i].second;
sub.insert(doub[i].second - doub[i].first);
y = min(y, co - *sub.rbegin());
upd(2*i+1, y);
upd(2*i+2, co);
add.erase(add.find(doub[i].first));
}
return ans;
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
costs.clear();
maxCost = K;
g.clear();
g.resize(N);
for(int i = 0; i < N-1; i++){
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
}
par.assign(N, -1);
dist.assign(N, 0);
dfs(X);
int ans = solveGreedy(X, Y);
int u = Y, last = -1;
while(u != -1){
ll d1 = dist[u], d2 = dist[Y]-dist[u];
ll myDist = min(d1, d2), upgrade = abs(d1-d2);
costs.emplace_back(0, upgrade);
maxCost -= myDist;
for(auto [v, w] : g[u]){
if(v == par[u] || v == last) continue;
collect(v, myDist+w, upgrade);
}
last = u;
u = par[u];
}
if(maxCost >= 0){
ans = max(ans, solve());
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
31428 KB |
Output is correct |
2 |
Correct |
99 ms |
37060 KB |
Output is correct |
3 |
Correct |
52 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
4 |
Halted |
0 ms |
0 KB |
- |