제출 #959223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959223		Ahmed57	Shortcut (IOI16_shortcut)	C++17	38 / 100	2043 ms	11608 KiB

shortcut

#include "bits/stdc++.h"
#include "shortcut.h"
using namespace std;
vector<pair<int,int>> adj[100001];
long long 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)));
    //cout<<ans<<endl;
    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<<ans<<endl;
    //cout<<an<<endl;
    if(an<b)ans = max(ans,MA(0,a,a)+c+MA(an+1,b,b));
    //cout<<ans<<endl;
    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<<an1<<" "<<an<<endl;
    ans = max(ans,suf[an]);
    //cout<<suf[an]<<endl;
    int an2 = an;
    if(an>a)ans = max(ans,MA(b,n-1,b)+c+MA(a,an-1,a));
    for(int i = a;i<=b;i++){
        int l = i , r = b , AN;
        while(l<=r){
            int mid = (l+r)/2;
            if(get_dist(i,mid)<=get_dist(mid,b)+c+get_dist(a,i)){
                AN = mid;
                l = mid+1;
            }else r = mid-1;
        }
        if(AN>i)ans = max(ans,D[i]+MA(i+1,AN,i));
        if(AN<b){
            ans = max(ans,D[i]+MA(AN+1,b,b)+get_dist(a,i)+c);
        }
    }
    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]);
            }
        }
    }
    long long ma = 0;
    long long 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-200);i<min(n,f+200);i++)lo.push_back(i);
    for(int i = max(0,s-200);i<min(n,s+200);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(10,{100,62,38,26,51,26,23,77,32},{80,74,91,20,42,99,90,5,4,18},8)<<endl;
}*/

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp: In function 'long long int shortcut(int, int, long long int)':
shortcut.cpp:52:9: warning: unused variable 'an1' [-Wunused-variable]
   52 |     int an1  = an;
      |         ^~~
shortcut.cpp:64:9: warning: unused variable 'an2' [-Wunused-variable]
   64 |     int an2 = an;
      |         ^~~
shortcut.cpp:77:34: warning: 'AN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             ans = max(ans,D[i]+MA(AN+1,b,b)+get_dist(a,i)+c);
      |                                ~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3