Submission #1206918

#TimeUsernameProblemLanguageResultExecution timeMemory
1206918_callmelucianCircus (Balkan15_CIRCUS)C++17
0 / 100
4104 ms527664 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 + 10; int dp[mn], p[mn], n, m; bool vis[mn]; int node (int layer, int i) { return layer * n + i; } void dijkstra (int source) { priority_queue<pii> pq; pq.emplace(0, source); for (int i = 0; i < 3 * n; i++) dp[i] = 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; for (int i = 0; i < n && p[i] <= p[u] - dp[u]; i++) addTransition(u, node(0, i), abs(p[i] - p[u]) - dp[u]); for (int i = n - 1; i >= 0 && p[i] >= p[u] + dp[u]; i--) addTransition(u, node(0, i), abs(p[i] - p[u]) - dp[u]); } } 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); assert(p[N] == m); /// run dijkstra dijkstra(N); } int minLength (int D) { int ans = INT_MAX; for (int i = 0; i < n; i++) if (dp[i] <= abs(p[i] - D)) ans = min(ans, abs(p[i] - 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

Compilation message (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...