제출 #1204699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204699		loiiii12358	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	328 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> ps,D,segl[2],segr[2];
void build(int id,int l,int r){
    if(l==r){
        segl[0][id]=segr[0][id]=0;
        segl[1][id]=segr[1][id]=D[l];
        return;
    }
    int m=l+(r-l)/2;
    build(id*2,l,m);
    build(id*2+1,m+1,r);
    segl[0][id]=max(segl[0][id*2],segl[1][id*2+1]+ps[m+1]-ps[l]);
    segr[0][id]=max(segr[0][id*2+1],segr[1][id*2]+ps[r]-ps[m]);
    segl[1][id]=max(segl[1][id*2],segl[1][id*2+1]+ps[m+1]-ps[l]);
    segr[1][id]=max(segr[1][id*2+1],segr[1][id*2]+ps[r]-ps[m]);
}
void init(int n){
    segl[0].resize(4*n);
    segr[1].resize(4*n);
    segl[1].resize(4*n);
    segr[0].resize(4*n);
    build(1,1,n);
}
int queryl(int id,int l,int r,int L,int R){
    if(l>R||r<L){
        return 0;
    }else if(l>=L&&r<=R){
        return ps[l]-ps[L]+segl[l!=L][id];
    }
    int m=l+(r-l)/2;
    return max(queryl(id*2,l,m,L,R),queryl(id*2+1,m+1,r,L,R));
}
int queryr(int id,int l,int r,int L,int R){
    if(l>R||r<L){
        return 0;
    }else if(l>=L&&r<=R){
        return ps[R]-ps[r]+segr[r!=R][id];
    }
    int m=l+(r-l)/2;
    return max(queryr(id*2,l,m,L,R),queryr(id*2+1,m+1,r,L,R));
}

vector<vector<int>> adj,tmpadj;

long long find_shortcut(int32_t n, std::vector<int32_t> l, std::vector<int32_t> d, int32_t c)
{
    if(n>100){
        return 0;
    }
    adj.resize(2*n+9,vector<int>(2*n+9,2e15));
    for(int i=0;i<n-1;i++){
        adj[i+1][i+2]=adj[i+2][i+1]=l[i];
    }
    for(int i=0;i<n;i++){
        adj[i+1][n+i+1]=adj[n+i+1][i+1]=d[i];
    }
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            for(int k=1;k<=2*n;k++){
                if(adj[j][k]>adj[j][i]+adj[i][k]){
                    adj[j][k]=adj[j][i]+adj[i][k];
                }
            }
        }
    }
    tmpadj=adj;
    int ans=0,tmp;
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            ans=max(ans,adj[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            adj=tmpadj;
            adj[i][j]=adj[j][i]=c;
            for(int k=1;k<=2*n;k++){
                for(int l=1;l<=2*n;l++){
                    if(adj[k][l]>adj[k][i]+adj[i][l]){
                        adj[k][l]=adj[k][i]+adj[i][l];
                    }
                }
            }
            for(int k=1;k<=2*n;k++){
                for(int l=1;l<=2*n;l++){
                    if(adj[k][l]>adj[k][j]+adj[j][l]){
                        adj[k][l]=adj[k][j]+adj[j][l];
                    }
                }
            }
            tmp=0;
            for(int k=1;k<=2*n;k++){
                for(int l=1;l<=2*n;l++){
                    tmp=max(tmp,adj[k][l]);
                }
            }
            ans=min(ans,tmp);
        }
    }
    return ans;
    // vector<int> pre, suf;
    // pre.resize(n+1,0);suf.resize(n+1,0);ps.resize(n+1,0);D.resize(n+1,0);
    // pre[1]=d[0];suf[n]=d[n-1];
    // for(int i=0;i<n-1;i++){
    //     pre[i+2]=max(pre[i+1]+l[i],(long long)d[i+1]);
    //     ps[i+2]=ps[i+1]+l[i];
    // }
    // for(int i=n-2;i>=0;i--){
    //     suf[i+1]=max(suf[i+2]+l[i],(long long)d[i]);
    // }
    // int tmp=0,L=1,R=1,cur;
    // for(int i=0;i<n-1;i++){
    //     tmp=max(tmp,pre[i+1]+l[i]+suf[i+2]);
    // }
    // for(int i=0;i<n;i++){
    //     D[i+1]=d[i];
    // }
    // init(n);
    // cur=tmp;
    // pair<int,int> pt={1,1},ma={0,0},ptnew,manew;
    // while(R<n){
    //     // cout << L << ' ' << R << ' ' << pt.first << ' ' << pt.second << ' ' << ma.first << ' ' << ma.second << ' ' << cur << '\n';
    //     R++;
    //     ptnew=pt;
    //     while(ps[ptnew.first+1]-ps[L]+c<=ps[R]-ps[ptnew.first+1]){
    //         ptnew.first++;
    //     }
    //     while(ps[R]-ps[ptnew.second]+c>ps[ptnew.second]-ps[L]&&ptnew.second<R){
    //         ptnew.second++;
    //     }
    //     manew={max(queryl(1,1,n,L,ptnew.first),pre[L]),max(queryr(1,1,n,ptnew.second,R),suf[R])};
    //     // cout << L << ' ' << R << ' ' << ptnew.first << ' ' << ptnew.second << ' ' << manew.first << ' ' << manew.second << ' ' << cur << '\n';
    //     // cout << max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]) << '\n';
    //     if(max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L])<cur||L==R-1){
    //         pt=ptnew;
    //         ma=manew;
    //         cur=max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]);
    //         tmp=min(tmp,cur);
    //         continue;
    //     }
    //     R--;
    //     L++;
    //     ptnew=pt;
    //     while(ps[ptnew.first+1]-ps[L]+c<=ps[R]-ps[ptnew.first+1]){
    //         ptnew.first++;
    //     }
    //     while(ps[R]-ps[ptnew.second]+c>ps[ptnew.second]-ps[L]&&ptnew.second<R){
    //         ptnew.second++;
    //     }
    //     manew={max(queryl(1,1,n,L,ptnew.first),pre[L]),max(queryr(1,1,n,ptnew.second,R),suf[R])};
    //     // cout << L << ' ' << R << ' ' << ptnew.first << ' ' << ptnew.second << ' ' << manew.first << ' ' << manew.second << ' ' << cur << '\n';
    //     // cout << max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]) << '\n';
    //     pt=ptnew;
    //     ma=manew;
    //     cur=max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]);
    //     tmp=min(tmp,cur);
    // }
    // return tmp;
}

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

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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