#include"closing.h"
#include<vector>
#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
int n,x,y;
ll k;
vector<pair<int,int>>nodes[200000];
ll distx[200000];
ll disty[200000];
void dfs1(int node,int par,ll*dists){
for(auto[ne,w]:nodes[node]){
if(ne==par)
continue;
dists[ne]=dists[node]+w;
dfs1(ne,node,dists);
}
}
int lvl1(){
vector<bool>vis(n);
int res=0;
ll kr=k;
priority_queue<pair<ll,int>>q;
q.push({0,x});
q.push({0,y});
vis[x]=true;
vis[y]=true;
while(q.size()){
int node=q.top().second;
ll cost=-q.top().first;
q.pop();
if(cost>kr)
break;
res++;
kr-=cost;
for(auto[ne,w]:nodes[node]){
if(vis[ne])
continue;
vis[ne]=true;
q.push({-min(distx[ne],disty[ne]),ne});
}
}
return res;
}
int get(multiset<ll>&s,ll money){
int res=0;
for(ll i:s){
if(i>money)
break;
res++;
money-=i;
}
return res;
}
int solve(vector<pair<ll,ll>>opts,ll money){
for(auto&[i,j]:opts)
swap(i,j);
sort(opts.begin(),opts.end());
for(auto&[i,j]:opts)
swap(i,j);
multiset<ll>s;
for(auto[i,j]:opts)
s.insert(i);
int res=get(s,money);
int res2=0;
for(auto[i,j]:opts){
money-=i;
s.erase(s.find(i));
s.insert(j);
res2++;
if(money<0)
break;
res=max(res,res2+get(s,money));
}
return res;
}
int lvl2(){
int cres=0;
ll money=k;
vector<pair<ll,ll>>opts;
for(int i=0;i<n;i++){
if(distx[i]+disty[i]==distx[y]){ // is on the path from x to y
cres++;
money-=min(distx[i],disty[i]);
opts.emplace_back(max(distx[i],disty[i])-min(distx[i],disty[i]),1e18);
}else{
opts.emplace_back(min(distx[i],disty[i]),max(distx[i],disty[i])-min(distx[i],disty[i]));
}
}
if(money<0)
return 0;
return cres+solve(opts,money);
}
int max_score(int N,int X,int Y,ll K,vector<int>U,vector<int>V,vector<int>W){
n=N;
x=X;
y=Y;
k=K;
for(int i=0;i<n;i++){
distx[i]=0;
disty[i]=0;
nodes[i].clear();
}
for(int i=0;i<n-1;i++){
nodes[U[i]].emplace_back(V[i],W[i]);
nodes[V[i]].emplace_back(U[i],W[i]);
}
dfs1(x,x,distx);
dfs1(y,y,disty);
return max(lvl1(),lvl2());
}
Compilation message
closing.cpp: In function 'int solve(std::vector<std::pair<long long int, long long int> >, ll)':
closing.cpp:65:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
65 | sort(opts.begin(),opts.end());
| ^~~~
| qsort
