Submission #1137455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137455		gyg	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	328 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 3e2 + 5;

int n, d;
arr<int, N> ext;
arr<vec<pii>, N> adj;

arr<arr<int, N>, N> dst;
void dfs(int u, int src, int pr = 0) {
    for (pii x : adj[u])
        if (x.fir != pr) dst[src][x.fir] = dst[src][u] + x.sec, dfs(x.fir, src, u);
}
void dst_cmp() {
    for (int u = 1; u <= n; u++)
        dfs(u, u);
}

vec<vec<int>> rq;
bool chck(int mn) {
    for (int u = 1; u <= n; u++)
        if (ext[u] > mn) return false;

    rq.clear();
    for (int u = 1; u <= n; u++) {
        vec<int> fr;
        for (int v = 1; v <= n; v++)
            if (v != u && dst[u][v] + ext[u] + ext[v] > mn) fr.push_back(v);
        if (fr.empty()) continue;

        if (fr[0] < u && fr.back() > u) return false;
        if (fr.back() < u) {
            int v = fr.back();
            rq.push_back({v, u, dst[u][v] + ext[u] + ext[v] - mn});
        } else {
            int v = fr[0];
            rq.push_back({u, v, dst[u][v] + ext[u] + ext[v] - mn});
        }
    }

    // for (vec<int> x : rq) cerr << x[0] << " " << x[1] << " " << x[2] << '\n';

    int l = 1, r = n, x = 0;
    for (vec<int> y : rq) 
        l = max(l, y[0]), r = min(r, y[1]), x = max(x, y[2]);

    // cerr << mn << ": " << l << " " << r << " " << x << '\n';

    if (l > r) return false;
    int sv = max(dst[l][r] - d, 0ll);
    return (sv >= x);
}
int srch() {
    int lw = 1, hg = 1e18;
    while (lw != hg) {
        int md = (lw + hg) / 2;
        if (chck(md)) hg = md;
        else lw = md + 1;
    }
    return lw;
}

int find_shortcut(signed _n, vec<signed> _edg, vec<signed> _ext, signed _d) {
    n = _n, d = _d;
    for (int u = 1; u < n; u++) 
        adj[u].push_back({u + 1, _edg[u - 1]}), adj[u + 1].push_back({u, _edg[u - 1]});
    for (int u = 1; u <= n; u++) ext[u] = _ext[u - 1];

    dst_cmp();
    return srch();
}

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