Submission #433995

#	Time	Username	Problem	Language	Result	Execution time	Memory
433995		Monchito	Shortcut (IOI16_shortcut)	C++14	23 / 100	2070 ms	8268 KiB

shortcut

#include "shortcut.h"
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;

const int MAXN = 1e3;
const ll INF = 1e18;

int N;
vector<int> G[MAXN];
vector<ll> W[MAXN];
vector<vector<ll>> dist(MAXN, vector<ll>(MAXN));

void BFS(int x) {
    vector<bool> vis(N, false);
    queue<pair<ll, int>> q;

    q.push(make_pair(0, x));

    while(!q.empty()) {
        pair<ll, int> p = q.front(); q.pop();
        int u = p.second;
        vis[u] = true;
        dist[x][u] = p.first;

        for(int i=0; i<(int)G[u].size(); i++) {
            int v = G[u][i];
            if(vis[v]) continue;

            ll w = W[u][i];
            q.push(make_pair(p.first + w, v));
        }
    }
}

void create_link(int u, int v, ll w) {
    G[u].push_back(v);
    W[u].push_back(w);
    G[v].push_back(u);
    W[v].push_back(w);
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    N = n;
    ll C = c;

    for(int i=0; i<n-1; i++) 
        create_link(i, i+1, l[i]);

    for(int i=0; i<n; i++) BFS(i);

    ll ret = INF;

    for(int l=0; l<n; l++) {
        for(int r=l+1; r<n; r++) {
            ll hi = -INF;

            for(int i=0; i<n; i++) {
                for(int j=i+1; j<n; j++) {
                    hi = max(hi, min(dist[i][j] + d[i] + d[j], d[i] + d[j] + dist[i][l] + C + dist[r][j]));
                }
            }
            ret = min(ret, hi);
        }
    }

    return ret;
}

• 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