/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
int max_score(int n,int x,int y,ll k,int U[],int V[],int W[]){
vector <vector <array <ll,2>>> a(n);
for(int i = 0;i + 1 < n;i++){
a[U[i]].push_back({V[i],W[i]});
a[V[i]].push_back({U[i],W[i]});
}
vector <array <ll,2>> sd;
vector <ll> d(n,inf);
vector <int> v(n,0);
priority_queue <array <ll,2>> q;
q.push({0,x});
v[x] = 1;d[x] = 0;
while(!q.empty()){
int i = q.top()[1];q.pop();
for(auto& [j,w] : a[i]){
d[j] = min(d[j],d[i] + w);
if(v[j] == 0){
q.push({-d[j],j});
v[j] = 1;
}
}
}
for(int i = 0;i < n;i++)sd.push_back({d[i],i});
d = vector <ll> (n,inf);
v = vector <int> (n,0);
q.push({0,y});
v[y] = 1;d[y] = 0;
while(!q.empty()){
int i = q.top()[1];q.pop();
for(auto& [j,w] : a[i]){
d[j] = min(d[j],d[i] + w);
if(v[j] == 0){
q.push({-d[j],j});
v[j] = 1;
}
}
}
for(int i = 0;i < n;i++)sd.push_back({d[i],i});
sort(sd.begin(),sd.end());
int ans = 0;
vector <ll> ct(n,0);
for(auto& [i,j] : sd){
k += ct[j];
k -= i;
ct[j] = i;
if(k >= 0)ans++;
}
return ans;
}
//signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);
//
// int t;cin >> t;
// while(t--){
// int n,x,y;ll k;
// cin >> n >> x >> y >> k;
//
// int u[n + 5],v[n + 5],w[n + 5];
// for(int i = 0;i + 1 < n;i++)cin >> u[i] >> v[i] >> w[i];
//
// cout << max_score(n,x,y,k,u,v,w) << endl;
// }
//
// return 0;
//}
Compilation message
/usr/bin/ld: /tmp/ccV792f6.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
