제출 #1206938

#제출 시각아이디문제언어결과실행 시간메모리
1206938_callmelucianCircus (Balkan15_CIRCUS)C++17
100 / 100
458 ms12260 KiB
#include <bits/stdc++.h> #include "circus.h" using namespace std; using ll = long long; using ld = long double; using pl = pair<ll,ll>; using pii = pair<int,int>; using tpl = tuple<int,int,int>; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 3e5 + 5; int dp[mn], p[mn], n, m; bool vis[mn]; vector<pii> sumOpt, difOpt; int node (int layer, int i) { return layer * n + i; } void dijkstra (int source) { priority_queue<pii> pq; pq.emplace(0, source); fill(dp, dp + 3 * n, INT_MAX), dp[source] = 0; function<void(int,int,int)> addTransition = [&] (int from, int to, int weight) { if (dp[from] + weight < dp[to]) { dp[to] = dp[from] + weight; pq.emplace(-dp[to], to); } }; while (pq.size()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = 1; int layer = u / n, idx = u % n; if (layer == 0) { /// real node // pass to suffix layer int sfx = lower_bound(p, p + n, dp[u] + p[idx]) - p; if (0 <= sfx && sfx < n) addTransition(u, node(1, sfx), p[sfx] - p[idx] - dp[u]); // pass to prefix layer int prf = upper_bound(p, p + n, p[idx] - dp[u]) - p - 1; if (0 <= prf && prf < n) addTransition(u, node(2, prf), p[idx] - p[prf] - dp[u]); } else if (layer == 1) { /// suffix node // pass to real layer addTransition(u, idx, 0); // pass to suffix layer if (idx + 1 < n) addTransition(u, node(1, idx + 1), p[idx + 1] - p[idx]); } else if (layer == 2) { /// prefix node // pass to real layer addTransition(u, idx, 0); // pass to prefix layer if (idx - 1 >= 0) addTransition(u, node(2, idx - 1), p[idx] - p[idx - 1]); } } } void init (int N, int M, int P[]) { /// input processing for (int i = 0; i < N; i++) p[i] = P[i]; p[N] = M, n = N + 1, m = M; sort(p, p + n); /// run dijkstra int source = lower_bound(p, p + n, M) - p; dijkstra(node(0, source)); /// preprocessing for (int i = 0; i < n; i++) { sumOpt.emplace_back(p[i] + dp[i], p[i]); difOpt.emplace_back(p[i] - dp[i], p[i]); } sort(all(sumOpt)), sort(all(difOpt)); for (int i = 1; i < n; i++) sumOpt[i].second = max(sumOpt[i].second, sumOpt[i - 1].second); for (int i = n - 2; i >= 0; i--) difOpt[i].second = min(difOpt[i].second, difOpt[i + 1].second); } int minLength (int D) { int ans = INT_MAX; int toLeft = upper_bound(all(sumOpt), make_pair(D, INT_MAX)) - sumOpt.begin() - 1; int toRight = lower_bound(all(difOpt), make_pair(D, 0)) - difOpt.begin(); if (0 <= toLeft && toLeft < n) ans = min(ans, D - sumOpt[toLeft].second); if (0 <= toRight && toRight < n) ans = min(ans, difOpt[toRight].second - D); return ans; } #ifdef LOCAL int main() { ios::sync_with_stdio(0); cin.tie(0); int N = 3, M = 8; int P[3] = {0, 3, 6}; init(N, M, P); cout << minLength(4) << " " << minLength(5) << "\n"; return 0; } #endif // LOCAL

컴파일 시 표준 에러 (stderr) 메시지

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~
#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...