Submission #425541

#	Time	Username	Problem	Language	Result	Execution time	Memory
425541		ngrace	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	332 KiB

shortcut

#include "shortcut.h"
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
#define pq priority_queue

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    v<v<long long>> adj(n,v<long long>(n, LLONG_MAX));
    for(int i=0;i<n-1;i++){
        adj[i][i+1] = l[i];
        adj[i+1][i] = l[i];
        adj[i][i]=0;
    }
    adj[n-1][n-1]=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+2;j<n;j++){
            adj[i][j] = adj[i][j-1]+adj[j-1][j];
            adj[j][i] = adj[i][j];
        }
    }

    long long out=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            long long dist=adj[i][j]+d[i]+d[j];
            if(dist>out) out=dist;
        }
    }

    v<long long> left(n,0);
    left[0]=d[0];
    for(int i=1;i<n;i++){
        left[i]=d[i];
        if(left[i-1]+l[i-1]>left[i]) left[i]=left[i-1]+l[i-1];
    }
    v<long long> right(n,0);
    right[n-1]=d[n-1];
    for(int i=n-2;i>=0;i--){
        right[i]=d[i];
        if(right[i+1]+l[i]>right[i]) right[i]=right[i+1]+l[i];
    }

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(adj[i][j]<=c) continue;
            long long diam=0;

            long long through = left[i]+right[j]+c;
            diam=through;
            if(diam>out) continue;

            long long allLeft=d[i]+((i==0)?0:(l[i-1]+left[i-1]));
            long long allRight=d[j]+((j==n-1)?0:(l[j]+right[j+1]));
            if(allLeft>diam) diam=allLeft;
            if(allRight>diam) diam=allRight;

            if(diam>out) continue;
            
            for(int a=i;a<=j;a++){
                long long toL = d[a] + adj[a][j] + c;
                long long toLNorm = d[a] + adj[a][i];
                if(toLNorm<toL) toL=toLNorm;

                long long toR = d[a] + adj[a][i] + c;
                long long toRNorm = d[a] + adj[a][j];
                if(toRNorm<toR) toR=toRNorm;

                if(toR+right[j]>diam && a!=j) diam=toR+right[j];
                if(toL+left[i]>diam && a!=i) diam=toL+left[i];
                if(diam>out) break;
            }

            if(diam>out) continue;

            for(int a=i;a<=j;a++){//should be able to only check both within i,j, but not working
                for(int b=a+1;b<=j;b++){
                    long long dist= adj[a][b]+d[a]+d[b];
                    long long dist2= d[a] + adj[a][i] + adj[b][j] + d[b] +c;
                    long long dist3= d[a] + adj[a][j] + adj[b][i] + d[b] +c;

                    if(dist2<dist) dist=dist2;
                    if(dist3<dist) dist=dist3;
                    if(dist>diam) diam=dist;
                    if(diam>out) break;
                }
            }
            if(diam<out){
                out=diam;
            }
        }
    }

    return out;
}

• 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