Submission #773716

#	Time	Username	Problem	Language	Result	Execution time	Memory
773716		PoonYaPat	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	212 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n;
ll ans=LLONG_MAX;
vector<pii> adj[1005];


ll find_shortcut(int N, vector<int> l, vector<int> d, int c) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        adj[i].push_back(pii(i+1,l[i]));
        adj[i+1].push_back(pii(i,l[i]));
    }

    vector<int> v;

    for (int i=0; i<n; ++i) {
        v.push_back(i);
        if (d[i]) {
            adj[i].push_back(pii(i+500,d[i]));
            adj[i+500].push_back(pii(i,d[i]));
            v.push_back(i+500);
        }
    }

    for (int l=0; l<n; ++l) {
        for (int r=l+1; r<n; ++r) {
            int sum=0;
            for (int i=l; i<r; ++i) sum+=d[i];
            if (c>sum) continue;

            //consider express in (l,r)
            adj[l].push_back(pii(r,c));
            adj[r].push_back(pii(l,c));

            ll mmax=0;

            for (auto st : v) {
                priority_queue<pii, vector<pii>, greater<pii>> q;
                ll dis[1005];
                bool vis[1005];

                for (int i=0; i<1003; ++i) dis[i]=1e18, vis[i]=false;

                dis[st]=0;
                q.push(pii(0,st));

                while (!q.empty()) {
                    ll node=q.top().second;
                    q.pop();
                    mmax=max(mmax,dis[node]);

                    if (vis[node]) continue;
                    vis[node]=true;

                    for (auto s : adj[node]) {
                        if (dis[s.first]>dis[node]+s.second) {
                            dis[s.first]=dis[node]+s.second;
                            q.push(pii(dis[s.first],s.first));
                        }
                    }
                }
            }
            ans=min(ans,mmax);

            adj[l].pop_back();
            adj[r].pop_back();
        }
    }

    ll mmax=0;

    for (auto st : v) {
        priority_queue<pii, vector<pii>, greater<pii>> q;
        ll dis[1005];
        bool vis[1005];

        for (int i=0; i<n+500; ++i) dis[i]=1e18, vis[i]=false;

        dis[st]=0;
        q.push(pii(0,st));

        while (!q.empty()) {
            ll node=q.top().second;
            q.pop();
            mmax=max(mmax,dis[node]);

            if (vis[node]) continue;
            vis[node]=true;

            for (auto s : adj[node]) {
                if (dis[s.first]>dis[node]+s.second) {
                    dis[s.first]=dis[node]+s.second;
                    q.push(pii(dis[s.first],s.first));
                }
            }
        }
    }
    ans=min(ans,mmax);

    return ans;
}

• 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