oj.uz

Submission #425520

# Submission time Handle Problem Language Result Execution time Memory
425520 2021-06-13T06:22:53 Z ngrace Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 292 KB 
#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 toR = d[a] + adj[a][j] + c + left[i];
                long long toRNorm = d[a] + adj[a][i]+left[i];
                if(toRNorm<toR) toR=toRNorm;

                long long toL = d[a] + adj[a][i] + c + right[j];
                long long toLNorm = d[a] + adj[a][j] + right[j];
                if(toLNorm<toL) toL=toLNorm;

                if(toR>diam && a!=i) diam=toR;
                if(toL>diam && a!=j) diam=toL;
                if(diam>out) break;
            }

            if(diam>out) continue;

            for(int a=i;a<=j;a++){
                for(int b=0;b<n;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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -