# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
240093 | 2020-06-18T02:21:04 Z | neihcr7j | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 74 ms | 110072 KB |
#include<bits/stdc++.h> #define oo 1000000000 #define maxm 4000000 #define maxn 50005 #define block 220 using namespace std; typedef long long ll; int n, m; int b[maxn], p[maxn]; vector < pair < int, int > > g[maxm]; int node(int u, int x) {return x * n + u;} int inode(int x) {return x % n;} int dnode(int x) {return (x - inode(x)) / n;} int dist[maxm]; int dijkstra() { priority_queue < pair < int, int > > p; fill(dist, dist + maxm, oo); dist[b[0]] = 0; p.push({0, b[0]}); while (!p.empty()) { int u = p.top().second; p.pop(); for (auto i : g[u]) { int v = i.first, w = i.second; if (dist[v] > dist[u] + w) { // cerr << u << ' ' << v << ' ' << w << '\n'; dist[v] = dist[u] + w; p.push({-dist[v], v}); } } } //for (int i = 0; i < 25; ++i) //cerr << i << ' ' << dist[i] << '\n'; return (dist[b[1]] != oo ? dist[b[1]] : -1); } int main(){ #define TASK "ABC" freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); ios_base::sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < m; ++i) cin >> b[i] >> p[i]; for (int j = 1; j <= block; ++j) for (int i = j; i < n; ++i) g[node(i, j)].push_back({node(i - j, j), 1}); for (int j = 1; j <= block; ++j) for (int i = 0; i + j < n; ++i) g[node(i, j)].push_back({node(i + j, j), 1}); for (int i = 0; i < n; ++i) for (int j = 1; j <= block; ++j) g[node(i, j)].push_back({i, 0}); for (int i = 0; i < m; ++i) if (p[i] <= block) g[b[i]].push_back({node(b[i], p[i]), 0}); for (int i = 0; i < m; ++i) if (p[i] > block) for (int j = b[i] % p[i]; j < n; j += p[i]) if (i != j) g[b[i]].push_back({j, abs(j - b[i]) / p[i]}); //for (int i = 0; i < 10; ++i) // for (auto j : g[i]) // cerr << i << ' ' << j.first << ' ' << j.second << '\n'; cout << dijkstra(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 73 ms | 109944 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 74 ms | 110048 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 73 ms | 110072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 71 ms | 109944 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 74 ms | 110072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |