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>
#define f first
#define s second
#define ent '\n'
using namespace std;
typedef long long ll;
const int mx=2e5+12;
vector<pair<int,ll>> g[mx];
ll need[mx];
ll prefmx[mx];
ll prefv[mx];
ll prefu[mx];
ll dmx[mx];
ll dv[mx];
ll du[mx];
int n;
ll k;
void dfs(int v,int p,ll d[]){
if(p<0){
d[v]=0;
}
dmx[v]=max(d[v],dmx[v]);
for(auto To:g[v]){
int to=To.f;
ll w=To.s;
if(to!=p){
d[to]=d[v]+w;
dfs(to,v,d);
}
}
}
ll get(int l,int r,ll pref[]){
if(!l)return pref[r];
return pref[r]-pref[l-1];
}
int max_score(int N, int x, int y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){
n=N,k=K;
int ans=2;
for(int i=0;i<n;i++){
g[i].clear();
dmx[i]=dv[i]=du[i]=0;
}
for(int i=0;i<n-1;i++){
g[V[i]].push_back({U[i],W[i]});
g[U[i]].push_back({V[i],W[i]});
}
dfs(x,-1,dv);
dfs(y,-1,du);
prefv[0]=dv[0],prefu[0]=du[0];
prefmx[0]=dmx[0];
for(int i=1;i<n;i++){
prefv[i]=prefv[i-1]+dv[i];
prefu[i]=prefu[i-1]+du[i];
prefmx[i]=prefmx[i-1]+dmx[i-1];
}
int cnt=0;
for(int l=x-1,r=y+1;l>=0 || r<n;){
cnt++;
if(r==n || l!=-1 && dv[l]<du[r]){
need[cnt]=need[cnt-1]+dv[l];
l--;
}
else{
need[cnt]=need[cnt-1]+du[r];
r++;
}
if(need[cnt]<=k){
ans=max(ans,cnt+2);
}
}
for(int i=cnt+1;i<=n;i++){
need[i]=1e18+1;
}
for(int l=x;l<y;l++){
for(int r=y;r>x;r--){
ll cost=0;
int pos=0;
if(l<r){
cost=get(x,l,prefv)+get(r,y,prefu);
}
else{
cost=get(x,r-1,prefv)+get(l+1,y,prefu)+get(r,l,prefmx);
}
for(int l=0,r=n;l<=r;){
int mid=l+r>>1;
if(need[mid]+cost<=k){
pos=mid;
l=mid+1;
}
else r=mid-1;
}
if(cost<=k)ans=max(ans,l-x+2+y-r+pos);
}
}
for(int l1=x;l1>=0;l1--){
for(int r1=x;r1<n;r1++){
for(int l2=y;l2>=0;l2--){
if(r1<y && l2>x)continue;
for(int r2=y;r2<n;r2++){
long long sum=0,cnt=0;
for(int i=0;i<n;i++){
long long t=0;
if(l1<=i && i<=r1){
t=dv[i];
cnt++;
}
if(l2<=i && i<=r2){
t=max(t,du[i]);
cnt++;
}
sum+=t;
}
if(sum<=k){
ans=max((ll)ans,cnt);
}
}
}
}
}
return ans;
}
Compilation message (stderr)
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:64:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
64 | if(r==n || l!=-1 && dv[l]<du[r]){
| ~~~~~~^~~~~~~~~~~~~~
closing.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | int mid=l+r>>1;
| ~^~
# | 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... |