oj.uz

Submission #959194

# Submission time Handle Problem Language Result Execution time Memory
959194 2024-04-07T15:59:03 Z Ahmed57 Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 11100 KB 
#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 D[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]);
    //cout<<an<<endl;
    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;
    }
    //cout<<an<<endl;
    ans = max(ans,suf[an]);
    int an2 = an;
    if(an>a)ans = max(ans,MA(b,n-1,b)+c+MA(a,an-1,a));
    if(an1<an2&&an1>a&&an2<b)ans = max(ans,sumpref[an2]-sumpref[an1]+D[an1]+D[an2]);
    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();
        D[i] = d[i];
    }
    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-2);i<min(n,f+2);i++)lo.push_back(i);
    for(int i = max(0,s-2);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(4,{2,2,2},{1,10,10,1},1)<<endl;
}*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB n = 4, 80 is a correct answer
2 Correct 2 ms 11100 KB n = 9, 110 is a correct answer
3 Correct 2 ms 11100 KB n = 4, 21 is a correct answer
4 Correct 2 ms 11100 KB n = 3, 4 is a correct answer
5 Correct 2 ms 11100 KB n = 2, 62 is a correct answer
6 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
7 Correct 2 ms 11100 KB n = 3, 29 is a correct answer
8 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
9 Correct 2 ms 11100 KB n = 2, 3 is a correct answer
10 Correct 2 ms 11100 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 11100 KB n = 2, 3000000000 is a correct answer
12 Incorrect 2 ms 11100 KB n = 3, incorrect answer: jury 3000000000 vs contestant 2000000001
13 Halted 0 ms 0 KB -