Submission #604992

#	Time	Username	Problem	Language	Result	Execution time	Memory
604992		MohamedFaresNebili	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	308 KiB

shortcut

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound

                void solve(int N, vector<int> e, vector<int> d, int c, int S, int i, int j, vector<ll>& D) {
                    priority_queue<pair<ll, int>,
                    vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
                    pq.push({d[S], S}); D.assign(N, 1000000000000000007); D[S] = d[S];
                    while(!pq.empty()) {
                        ll A = pq.top().ss, W = pq.top().ff; pq.pop();
                        if(W > D[A]) continue;
                        int V = A + 1;
                        if(A < N - 1 && D[V] > D[A] + e[A]) {
                            D[V] = D[A] + e[A];
                            pq.push({D[V], V});
                        }
                        V = A - 1;
                        if(A > 0 && D[V] > D[A] + e[A - 1]) {
                            D[V] = D[A] + e[A - 1];
                            pq.push({D[V], V});
                        }
                        if(A == i && D[A] + c < D[j]) {
                            D[j] = D[A] + c;
                            pq.push({D[j], j});
                        }
                        if(A == j && D[A] + c < D[i]) {
                            D[i] = D[A] + c;
                            pq.push({D[i], i});
                        }
                    }
                }

                long long find_shortcut(int N, vector<int> e, vector<int> d, int c) {
                    ll best = 1000000000000000007;
                    for(int i = 0; i < N; i++) {
                        for(int j = i + 1; j < N; j++) {
                            vector<ll> D;
                            solve(N, e, d, c, 0, i, j, D);
                            int V = 0;
                            for(int k = 1; k < N; k++) D[k] += d[k];
                            for(int k = 0; k < N; k++) {
                                if(D[k] >= D[V]) V = k;
                            }
                            solve(N, e, d, c, V, i, j, D);
                            ll ans = 0;
                            for(int k = 0; k < N; k++) {
                                if(k == V) continue;
                                D[k] += d[k];
                            }
                            for(int k = 0; k < N; k++)
                                ans = max(ans, D[k]);
                            best = min(best, ans);
                        }
                    }
                    return best;
                }

• 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