#include "bits/stdc++.h"
#include "shortcut.h"
using namespace std;
vector<pair<int,int>> adj[100001];
int maa = -1 , lol = -1;
void dfs(int i,int pr,int dep){
if(maa<dep){
maa = dep;
lol = i;
}
for(auto j:adj[i]){
if(j.first==pr)continue;
dfs(j.first,i,dep+j.second);
}
}
int cnt = 0;
long long oo = 1e18;
int n;
long long sumpref[100001],sumsuf[100001];
long long tbpref[100001][20],tbsuf[100001][20];
long long pref[100001];long long suf[100001];
long long get_dist(int a,int b){
return sumpref[b]-sumpref[a];
}
long long MA(int a,int b,int c){
int lg = __lg(b-a+1);
if(c<=a){
return max(tbpref[a][lg],tbpref[b-(1<<lg)+1][lg])-sumpref[c];
}else{
return max(tbsuf[a][lg],tbsuf[b-(1<<lg)+1][lg])-sumsuf[c];
}
}
long long shortcut(int a,int b,long long c){
if(a>b)swap(a,b);
long long ans = 0;
int l = a , r = b , an = -1;
ans = max(ans,MA(b,n-1,b)+MA(0,a,a)+min(c,get_dist(a,b)));
while(l<=r){
int mid = (l+r)/2;
if(get_dist(a,mid)<=get_dist(mid,b)+c){
an = mid;
l = mid+1;
}else r = mid-1;
}
ans = max(ans,pref[an]);
if(an<b)ans = max(ans,MA(0,a,a)+c+MA(an+1,b,b));
int an1 = an;
l = a , r = b , an = -1;
while(l<=r){
int mid = (l+r)/2;
if(get_dist(mid,b)<=get_dist(a,mid)+c){
an = mid;
r = mid-1;
}else l = mid+1;
}
ans = max(ans,suf[an]);
if(an>a)ans = max(ans,MA(b,n-1,b)+c+MA(a,an-1,a));
return ans;
}
long long find_shortcut(int N,vector<int> l, vector<int> d, int c){
n = N;
for(int i = 0;i<n;i++){
adj[i].clear();
}
for(int i = 1;i<n;i++){
adj[i-1].push_back({i,l[i-1]});
adj[i].push_back({i-1,l[i-1]});
}
sumpref[0] = 0;
for(int i = 1;i<n;i++){
sumpref[i] = sumpref[i-1]+l[i-1];
}
sumsuf[n-1] = 0;
for(int i = n-2;i>=0;i--){
sumsuf[i] = sumsuf[i+1]+l[i];
}
for(int i = 0;i<n;i++){
tbpref[i][0] = sumpref[i]+d[i];
tbsuf[i][0] = sumsuf[i]+d[i];
}
for(int i =n-1;i>=0;i--){
for(int j =1;j<20;j++){
if(i+(1<<j)-1<n){
tbpref[i][j] = max(tbpref[i][j-1],tbpref[i+(1<<(j-1))][j-1]);
tbsuf[i][j] = max(tbsuf[i][j-1],tbsuf[i+(1<<(j-1))][j-1]);
}
}
}
int ma = 0;
int lola = 0;
for(int i = 0;i<n;i++){
lola = max(lola,ma+d[i]);
ma = max(ma,d[i]);
pref[i] = lola;
if(i<n-1){
ma+=l[i];
}
}
ma = 0;
lola = 0;
for(int i = n-1;i>=0;i--){
lola = max(lola,ma+d[i]);
ma = max(ma,d[i]);
suf[i] = lola;
if(i>0){
ma+=l[i-1];
}
}
cnt = n;
int pr[2*n+1] = {0};
for(int i = 0;i<n;i++){
if(d[i]){
pr[cnt] = i;
adj[cnt].clear();
adj[i].push_back({cnt,d[i]});
adj[cnt].push_back({i,d[i]});
cnt++;
}
}
dfs(0,-1,0);
maa = -1;
int f = lol;
dfs(lol,-1,0);
int s = lol;
vector<int> lo;
if(f>=n)f = pr[f];
if(s>=n)s = pr[s];
for(int i = max(0,f-1);i<min(n,f+2);i++)lo.push_back(i);
for(int i = max(0,s-1);i<min(n,s+2);i++)lo.push_back(i);
long long mi = oo;
for(int i = 0;i<n;i++){
for(auto j:lo){
mi = min(mi,shortcut(i,j,c));
}
}
return mi;
}
/*int main(){
cout<<find_shortcut(3, {1, 1}, {1, 1, 1}, 3)<<endl;
}*/
Compilation message
shortcut.cpp: In function 'long long int shortcut(int, int, long long int)':
shortcut.cpp:48:9: warning: unused variable 'an1' [-Wunused-variable]
48 | int an1 = an;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10332 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
5 ms |
10332 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
2 ms |
10364 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
