Submission #1265592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265592		gustavo_d	Shortcut (IOI16_shortcut)	C++20	0 / 100	11 ms	23876 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

typedef long long ll;

const int MAXN = 1e6;

ll pfAll[MAXN], sfAll[MAXN], pos[MAXN];
int pfSrc[MAXN], sfSrc[MAXN];

ll dist[MAXN];
vector<pair<int, ll>> adj[MAXN];
int N;

void Dijkstra(int src) {
    for (int i=0; i<N; i++) dist[i] = 1e18;
    dist[src] = 0;
    priority_queue<
        pair<ll, int>,
        vector<pair<ll, int>>,
        greater<pair<ll, int>>
    > pq; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (d > dist[v]) continue;
        for (auto [viz, w] : adj[v]) {
            // cout << v << "->" << viz << endl;
            // cout << dist[viz] << ' ' << d << ' ' << w << endl;
            if (dist[viz] > d + w) {
                // cout << "ok" << endl;
                dist[viz] = d + w;
                pq.push({dist[viz], viz});
            }
        }
    }
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    pfAll[0] = d[0]; pfSrc[0] = 0;
    for (int i=0; i<n-1; i++) {
        pfAll[i+1] = max((ll)d[i+1], pfAll[i] + l[i]);
        pfSrc[i+1] = (d[i+1] > pfAll[i] + l[i] ? i+1 : pfSrc[i]);
    }
    sfAll[n-1] = d[n-1]; sfSrc[n-1] = n-1;
    for (int i=n-2; i>=0; i--) {
        sfAll[i] = max((ll)d[i], sfAll[i+1] + l[i]);
        sfSrc[i] = (d[i] > sfAll[i+1] + l[i] ? i : sfSrc[i+1]);
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        ans = (pfAll[i] + sfAll[i] > pfAll[ans] + sfAll[ans] ? i : ans);
    }
    vector<ll> diam; bool left = true, right = true;
    if (d[pfSrc[ans]] > 0) {
        left = false;
        diam.push_back(d[pfSrc[ans]]);
    }
    for (int i=pfSrc[ans]; i<sfSrc[ans]; i++) {
        diam.push_back(l[i]);
    }
    if (d[sfSrc[ans]] > 0) {
        diam.push_back(d[sfSrc[ans]]);
        right = false;
    }

    N = n = (int)diam.size() + 1;
    for (int i=0; i<n-1; i++) {
        adj[i].emplace_back(i+1, diam[i]);
        adj[i+1].emplace_back(i, diam[i]);
    }
    // pos[0] = 0;
    // for (int i=1; i<n; i++) pos[i] = pos[i-1] + diam[i-1];

    ll res = 1e18;
    for (int i=(!left); i<n; i++) {
        for (int j=i; j<n-(!right); j++) {
            adj[i].emplace_back(j, c);
            adj[j].emplace_back(i, c);

            Dijkstra(0);
            int p1 = 0;
            for (int i=0; i<n; i++) {
                if (dist[i] > dist[p1]) i = p1;
            }
            Dijkstra(p1);
            ll tmp = 0;
            for (int i=0; i<n; i++) {
                tmp = max(tmp, dist[i]);
            }
            res = min(res, tmp);

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

    return res;

    // for (int i=0; i<n; i++) cout << pos[i] << ' ';
    // cout << endl;

    // ll lAns = c, rAns = pos[n-1], res = pos[n-1];
    // while (lAns <= rAns) {
    //     ll mid = (lAns + rAns) / 2;
    //     cout << lAns << ' ' << rAns << ':' << mid << endl;
    //     bool check = false; int k = 0;
    //     for (int i=0; i<n; i++) {
    //         if (pos[i] < mid) k = i;
    //     }
    //     cout << k << endl;

    //     if (k == n-1) check = true;
    //     for (int i=0+(!left), j=0; i<=k and !check; i++) {
    //         bool stop = false;
    //         while (!stop and pos[i] + c + pos[n-1] - pos[j] > mid) {
    //             if (j == n-1-(!right)) stop = true;
    //             j++;
    //         }
    //         if (stop) break;
    //         if (pos[i] + c + max(pos[j] - pos[k], pos[n-1]-pos[j]) <= mid) {
    //             cout << i << ' ' << j << endl;
    //             check = true;
    //         }
    //     }

    //     if (check) {
    //         res = mid;
    //         rAns = mid-1;
    //     } else lAns = mid+1;
    // }

    // return res;
}

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