Submission #425477

#	Time	Username	Problem	Language	Result	Execution time	Memory
425477		ngrace	Shortcut (IOI16_shortcut)	C++14	23 / 100	2050 ms	2436 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;
    v<v<long long>> large;
    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;
            large.push_back({-dist, i, j});
        }
    }
    sort(large.begin(),large.end());

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            long long diam=0;
            for(v<long long> it: large){
                long long a=it[1];
                long long b=it[2];

                long long dist= -it[0];
                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: 9 / 9
• Subtask 2: 14 / 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