Submission #1230093

#TimeUsernameProblemLanguageResultExecution timeMemory
1230093viduxShortcut (IOI16_shortcut)C++17
23 / 100
2086 ms1440 KiB
#include "shortcut.h" #include <bits/stdc++.h> #define fi first #define se second #define ALL(x) (x.begin()), (x.end()) #define DEBUG(x) cerr << #x << ": " << x << endl; #define DEBUG_ARR(x) cerr << #x << ": "; for (auto &y : x) cout << y << " "; cout << endl; #define SZ(x) ((int)x.size()) using namespace std; typedef long long ll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef pair<ll, ll> pll; long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { vvl adj(n, vl(n, 1e18)); for (int i = 0; i < n-1; i++) adj[i][i+1] = adj[i+1][i] = l[i]; for (int i = 0; i < n; i++) adj[i][i] = 0; for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { adj[i][j] = adj[j][i] = min(adj[i][j], adj[i][k]+adj[k][j]); } } } ll ans = 1e18; for (int l = 0; l < n; l++) { for (int r = l+1; r < n; r++) { vvl adj2 = adj; adj2[l][r] = adj2[r][l] = min(adj[l][r], (ll)c); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { adj2[i][j] = adj2[j][i] = min(adj2[i][j], adj2[i][l]+adj2[l][r]+adj2[r][j]); } } ll mx = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { mx = max(adj2[i][j]+d[i]+d[j], mx); } } ans = min(ans, mx); } } return ans; }

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
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...