# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
753048 | 2023-06-04T13:49:14 Z | MohamedFaresNebili | Cyberland (APIO23_cyberland) | C++17 | 648 ms | 20288 KB |
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx2") using namespace std; using ll = long long; using pi = pair<double, pair<int, int>>; const ll M = 1000000000000000005; const double epsilon = 0.000001; double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { k = min(k, 70); double d[n][k + 1]; for(int l = 0; l < n; l++) for(int i = 0; i <= k; i++) d[l][i] = M; vector<pair<int, int>> adj[n]; d[0][0] = 0; for(int l = 0; l < m; l++) { adj[x[l]].push_back({y[l], c[l]}); adj[y[l]].push_back({x[l], c[l]}); } queue<int> q; vector<bool> vis(n, 0); vis[0] = 1; q.push(0); while(!q.empty()) { int u = q.front(); q.pop(); if(arr[u] == 0) d[u][0] = 0; if(u == h) continue; for(auto v : adj[u]) { if(vis[v.first]) continue; vis[v.first] = 1; q.push(v.first); } } for(int l = 0; l < n; l++) if(arr[l] == 0) d[l][0] = 0; for(int l = 0; l <= k; l++) { priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq; for(int i = 0; i < n; i++) if(i != h && d[i][l] != M) pq.push({d[i][l], i}); while(!pq.empty()) { double w = pq.top().first; int u = pq.top().second; pq.pop(); if(u == h) continue; for(auto v : adj[u]) { if(arr[v.first] == 2 && l < k) d[v.first][l + 1] = min(d[v.first][l + 1], (d[u][l] + v.second) / 2.0); if(d[u][l] + v.second < d[v.first][l]) { d[v.first][l] = d[u][l] + v.second; pq.push({d[v.first][l], v.first}); } } } } double res = M; for(int l = 0; l <= k; l++) res = min(res, d[h][l]); if(res == M) return -1; return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 38 ms | 408 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 708 KB | Correct. |
2 | Correct | 35 ms | 612 KB | Correct. |
3 | Correct | 32 ms | 596 KB | Correct. |
4 | Correct | 36 ms | 788 KB | Correct. |
5 | Correct | 35 ms | 668 KB | Correct. |
6 | Correct | 29 ms | 3532 KB | Correct. |
7 | Correct | 38 ms | 3516 KB | Correct. |
8 | Correct | 20 ms | 6868 KB | Correct. |
9 | Correct | 30 ms | 340 KB | Correct. |
10 | Correct | 30 ms | 368 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 35 ms | 788 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 648 ms | 20288 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 712 KB | Correct. |
2 | Correct | 33 ms | 596 KB | Correct. |
3 | Correct | 32 ms | 676 KB | Correct. |
4 | Correct | 34 ms | 3540 KB | Correct. |
5 | Correct | 27 ms | 340 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 640 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 204 ms | 576 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 416 ms | 988 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |