#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long N = 200010;
vector <pair <long long, long long>> g[N];
long long mark[N];
long long custox[N], custoy[N];
void dfs_x(int v, int p){
for(auto [x, w] : g[v]){
if(x == p)
continue;
custox[x] = custox[v] + w;
dfs_x(x, v);
}
return;
}
void dfs_y(int v, int p){
for(auto [x, w] : g[v]){
if(x == p)
continue;
custoy[x] = custoy[v] + w;
dfs_y(x, v);
}
return;
}
int l[N], r[N];
int max_score(int n, int X, int Y, long long k,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
for(int i = 0;i < n;i++){
g[i].clear();
mark[i] = 0;
custox[i] = custoy[i] = 0;
}
for(long long i = 0;i < n-1;i++){
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
priority_queue <pair <long long, long long>> pq;
pq.push({0, X});
pq.push({0, Y});
long long ans = 0, sum = 0;;
while(!pq.empty()){
auto [w, v] = pq.top();
pq.pop();
if(mark[v])
continue;
w *= -1;
if(sum+w > k){
break;
}
sum += w;
ans++;
mark[v] = 1;
for(auto [x, ww] : g[v]){
if(mark[x])
continue;
pq.push({-(ww+w), x});
}
}
dfs_x(X, X);
dfs_y(Y, Y);
for(int i = 0;i < n;i++){
l[i] = min(custox[i], custoy[i]);
r[i] = max(custox[i], custoy[i]) - l[i];
//cout << l[i] << ' ' << r[i] << '\n';
mark[i] = 0;
}
priority_queue <array <long long, 3>> pqq;
long long res = 0;
long long custo = 0;
for(int i = X;i <= Y;i++){
pqq.push({-r[i], i, 1ll});
custo += l[i];
mark[i] = 1;
res++;
}
if(custo > k)
return ans;
if(X > 0){
pqq.push({-l[X-1], X-1, 0});
}
if(Y < n-1){
pqq.push({-l[Y+1], Y+1, 0});
}
while(!pqq.empty()){
auto [val, v, tp] = pqq.top();
pqq.pop();
val *= -1;
//cout << val << ' ' << v << ' ' << tp << '\n';
if(val+custo > k)
break;
custo += val;
res++;
if(tp == 0){
mark[v] = 1;
pqq.push({-r[v], v, 1ll});
for(auto [x, w] : g[v]){
if(mark[x])
continue;
mark[x] = 1;
pqq.push({-l[x], x, 0ll});
}
}
}
ans = max(res, ans);
return ans;
}
# | 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... |