Submission #915746

#TimeUsernameProblemLanguageResultExecution timeMemory
915746WansurClosing Time (IOI23_closing)C++17
0 / 100
1031 ms35388 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...