Submission #1219948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219948		LIA	Shortcut (IOI16_shortcut)	C++17	0 / 100	2094 ms	328 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e18;
ll N;
ll nodes;
vvpll g;
ll find() {
    ll ans = 0;
    loop(s, 0, nodes) {
        vll dist(nodes, inf);
        dist[s] = 0;
        priority_queue<pll, vpll, greater<pll>> pq;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, w] : g[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
        loop(i, 0, nodes) {
            ans = max(ans, dist[i]);
        }
    }
    return ans;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    ll cnt =n ;
    g.resize(n*2);
    loop(i,0,n-1) {
        g[i].push_back({i+1, l[i]});
        g[i+1].push_back({i, l[i]});
        if (d[i]) {
            g[i].push_back({cnt, d[i]});
            g[cnt].push_back({i, d[i]});

            cnt++;
        }
    }
    if (d[n-1]) {
        g[n-1].push_back({cnt, d[n-1]});
        g[cnt].push_back({n-1, d[n-1]});

        cnt++;
    }
    N=n;
    ll ans = inf;
    nodes = cnt;
    loop(i,0,n) {
        loop(j,i+1, n) {
            g[i].push_back({j,c});
            g[j].push_back({i,c});
            ans = min(ans, find());
            g[i].pop_back();
            g[j].pop_back();
        }
    }
    return ans;
}
/*
4 10

10 20 20

0 40

0 30
*/

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