Submission #1263124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263124		silentloop	Shortcut (IOI16_shortcut)	C++20	23 / 100	2097 ms	47432 KiB

shortcut

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;

const int MAXN = 2000001;
vector<pair<ll, ll>> grafo[MAXN];
ll N;
vector<int> D, L;

vector<ll> dijk(ll nod)
{
    priority_queue<pair<ll, ll>> pq;
    vector<ll> dist(N * 2 + 1, LLONG_MAX), proc(N * 2 + 1, 0);
    pq.push({0, nod});
    dist[nod] = 0;
    while (pq.size())
    {
        nod = pq.top().se;
        pq.pop();
        if (proc[nod])
            continue;
        proc[nod] = 1;
        for (auto k : grafo[nod])
        {
            if (dist[k.fr] > dist[nod] + k.se)
            {
                dist[k.fr] = dist[nod] + k.se;
                pq.push({-dist[k.fr], k.fr});
            }
        }
    }
    return dist;
}

vector<ll> dis0;
ll calc(ll a, ll b)
{
    ll i, n = N, ma = 0, j, act, dis;
    vector<ll> disa = dijk(a), disb = dijk(b);
    for (i = 0; i < n; i++)
    {
        ma = max(ma, 1ll * D[i]);
        for (j = i + 1; j < n; j++)
        {
            dis = abs(dis0[i] - dis0[j]);
            dis = min(disa[i] + disa[j], dis);
            dis = min(dis, disb[i] + disb[j]);
            dis = dis + D[i] + D[j];
            ma = max(dis, ma);
        }
    }
    return ma;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    N = n;
    ll i, j, mi = LLONG_MAX;
    D = d;
    L = l;
    for (i = 0; i < sz(l); i++)
    {
        grafo[i].pb({i + 1, l[i]});
        grafo[i + 1].pb({i, l[i]});
    }
    for (i = 0; i < n; i++)
    {
        if (d[i] > 0)
        {
            grafo[i].pb({i + n, d[i]});
            grafo[i + n].pb({i, d[i]});
        }
    }
    dis0 = dijk(0);
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            grafo[i].pb({j, c});
            grafo[j].pb({i, c});
            mi = min(mi, calc(i, j));
            grafo[i].pop_back();
            grafo[j].pop_back();
        }
    }
    return mi;
}

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: 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