Submission #1080806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080806		ALeonidou	Shortcut (IOI16_shortcut)	C++17	9 / 100	2100 ms	600 KiB

shortcut

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

using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()

typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
 
#define INF 100000000000000000

vector <vii> adj;
priority_queue <ii, vii, greater<ii> > pq;
vi dis;
ll dijkstra(ll s){      //O(nlogn)
    for (ll i =0; i<sz(dis); i++) dis[i] = INF;
    dis[s] = 0;
    pq.push(ii(0, s));
    while (!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll c = f.S, w = f.F;
        if (w > dis[c]) continue;
        for (ll i =0; i<sz(adj[c]); i++){
            ii v = adj[c][i];
            if (v.S + dis[c] < dis[v.F]){
                dis[v.F] = v.S + dis[c];
                pq.push(ii(dis[v.F], v.F));
            }
        }
    }
    ll maxi = 0;
    for (ll i =0; i<sz(dis); i++){
        if (maxi < dis[i]){
            maxi = dis[i];
        }
    }
    return maxi;
}

ll find_shortcut(int N, vector<int> l, vector<int> d, int C)
{
    ll c = C;
    ll n = N;
    ll m = n;
    for (ll i =0; i<sz(d); i++){
        if (d[i]) m++;
    }
    adj.assign(m, vii());
    for (ll i =0; i<sz(l); i++){
        adj[i].pb(ii(i+1, l[i]));
        adj[i+1].pb(ii(i, l[i]));
    }
    ll tmp_cnt = 0;
    for (ll i =0; i<sz(d); i++){
        if (!d[i]) continue;
        adj[i].pb(ii(tmp_cnt+n, d[i]));
        adj[tmp_cnt+n].pb(ii(i, d[i]));
        tmp_cnt++;
    }
    dis.resize(sz(adj));

    ll ans = INF;
    for (ll i =0; i<n; i++){    //O(n^4 * logn)
        for (ll j = i+1; j<n; j++){
            adj[i].pb(ii(j,c));
            adj[j].pb(ii(i,c));

            ll cur = 0;
            for (ll k =0; k<sz(adj); k++){
                cur = max(cur, dijkstra(k));
            }
            ans = min(ans, cur);

            adj[i].pop_back();
            adj[j].pop_back();
        }
    }
    
    return ans;
}

/*
4 10
10 20 20
0 40 0 30

20 30
10 10 10 20 10 30 10 10 5 10 10 10 20 10 30 10 10 5 5
20 10 30 20 10 40 20 40 30 20 20 10 30 20 10 40 20 40 30 20

*/

• Subtask 1: 9 / 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