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<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
#include <vector>
const int MN=3e5;
vector<pair<int,ll>>v[MN];
ll distx[MN],disty[MN];
void dfsx(int a, int p){
for(auto t:v[a]){
if(p==t.ff)continue;
distx[t.ff]=distx[a]+t.ss;
dfsx(t.ff,a);
}
}
void dfsy(int a, int p){
for(auto t:v[a]){
if(p==t.ff)continue;
disty[t.ff]=disty[a]+t.ss;
dfsy(t.ff,a);
}
}
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++){
disty[i]=0;
distx[i]=0;
}
for(int i=0;i<N;i++){
v[i].clear();
}
ll k=K;
for(int i=0;i<N-1;i++){
int a=U[i];
int b=V[i];
ll c=W[i];
v[a].pb({b,c});
v[b].pb({a,c});
}
dfsx(X,-1);
dfsy(Y,-1);
vector<ll>vx,vy;
for(int i=0;i<N;i++){
vx.pb(distx[i]);
vy.pb(disty[i]);
}
sort(vx.begin(),vx.end());
sort(vy.begin(),vy.end());
for(int i=1;i<N;i++){
vy[i]+=vy[i-1];
}
for(int i=1;i<N;i++){
//vy[i]+=vy[i-1];
}
ll s=0;
ll ans=0;
for(ll i=0;i<N;i++){
s+=vx[i];
if(s>k)break;
auto it=upper_bound(vy.begin(),vy.end(),k-s+1);
it--;
int g=it-vy.begin();
ans=max(ans,i+g+2);
////cout<<vy[it];
// return 0;
}
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... |