Submission #1253436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253436		antonn	Shortcut (IOI16_shortcut)	C++20	0 / 100	2095 ms	328 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
bool assign_min(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool assign_max(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/*
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
*/

int n;
vector<vector<pair<int, int>>> g;
vector<ll> dist;

int get_far(int u) {
    vector<int> vis(2 * n + 1);
    dist.assign(2 * n + 1, 1e18);
    priority_queue<pair<ll, ll>> pq;
    pq.push({0, u});
    dist[u] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, c] : g[u]) {
            if (dist[u] + c < dist[v]) {
                dist[v] = dist[u] + c;
                pq.push({-dist[v], v});
            }
        }
    }
    int best = u;
    for (int i = 1; i <= 2 * n; i++) {
        if (dist[i] != 1e18 && dist[i] > dist[best]) {
            best = i;
        }
    }
    return best;
}

ll solve(vector<array<ll, 3>> edges, bool print = 0) {
    g.assign(2 * n + 1, {});
    for (auto [a, b, c] : edges) {
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    ll ans = 0;
    for (int u = 1; u <= 2 * n; ++u) {
        int v = get_far(u);
        ans = max(ans, dist[v]);
    }
    return ans;
}

ll find_shortcut(int N, vector<int> l, vector<int> d, int c) {
    n = N;
    vector<array<ll, 3>> edges;
    for (int i = 1; i <= n; i++) {
        if (d[i - 1] != 0) {
            edges.push_back({i, n + i, d[i - 1]});
        }
        if (i < n) {
            edges.push_back({i, i + 1, l[i - 1]});
        }
    }
    
    ll ans = solve(edges);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            edges.push_back({i, j, c});
            ans = min(ans, solve(edges, (i == 1 && j == 7)));
            edges.pop_back();
        }
    }
    return ans;
}

Compilation message (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