제출 #1137582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137582		gyg	Shortcut (IOI16_shortcut)	C++20	31 / 100	1899 ms	1044 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, INF = 1e18;

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);
}

int dmtr_cmp() {
    int ans = INF;
    for (int a = 1; a <= n; a++) {
        for (int b = a + 1; b <= n; b++) {
            int dmtr = 0;
            for (int u = 1; u <= n; u++) {
                dmtr = max(dmtr, ext[u]);
                for (int v = u + 1; v <= n; v++) {
                    int sp = min({ext[u] + dst[u][v] + ext[v], 
                                  ext[u] + dst[u][a] + d + dst[b][v] + ext[v],
                                  ext[u] + dst[u][b] + d + dst[a][v] + ext[v]});
                    dmtr = max(dmtr, sp);
                }
            }
            ans = min(ans, dmtr);
        }
    }
    return ans;
}

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 dmtr_cmp();
}

컴파일 시 표준 에러 (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: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3