Submission #155971

#TimeUsernameProblemLanguageResultExecution timeMemory
155971MinnakhmetovOBELISK (NOI14_obelisk)C++14
5 / 25
176 ms53504 KiB
#include <bits/stdc++.h> #define ll long long #define all(aaa) aaa.begin(), aaa.end() using namespace std; struct E { int to, w; }; const int K = 11, M = 1e6, C = 105, Z = 52, INF = 1e9; vector<E> g[M]; int d[M]; bool hole[K][C][C]; int getId(int x, int y, int z, int k) { return k * C * C * 3 + x * C * 3 + y * 3 + z; } void addEdge(int a, int b, int c) { g[a].push_back({b, c}); g[b].push_back({a, c}); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int m, k, sx, sy, ex, ey; cin >> k >> m >> sx >> sy >> ex >> ey; sx += Z; sy += Z; ex += Z; ey += Z; for (int i = k - 1; i > 0; i--) { int h; cin >> h; while (h--) { int x, y; cin >> x >> y; x += Z; y += Z; hole[i][x][y] = 1; g[getId(x, y, 0, i)].push_back({getId(x, y, 0, i - 1), 0}); } } for (int i = 0; i < k; i++) { for (int x = 0; x < C; x++) { for (int y = 0; y < C; y++) { if (m == 1) { addEdge(getId(x, y, 0, i), getId(x, y, 1, i), 0); addEdge(getId(x, y, 1, i), getId(x, y, 2, i), 0); } if (x + 1 < C) { addEdge(getId(x, y, 0, i), getId(x + 1, y, 1, i), 1); addEdge(getId(x, y, 2, i), getId(x + 1, y, 2, i), 1); } if (y + 1 < C) { addEdge(getId(x, y, 0, i), getId(x, y + 1, 2, i), 1); addEdge(getId(x, y, 1, i), getId(x, y + 1, 1, i), 1); } if (x + m < C) { addEdge(getId(x, y, 1, i), getId(x + m, y, 0, i), 1); } if (y + m < C) { addEdge(getId(x, y, 2, i), getId(x, y + m, 0, i), 1); } } } } fill(d, d + M, -1); int start = getId(sx, sy, 0, k - 1); d[start] = 0; deque<int> q; q.push_back(start); while (!q.empty()) { int node = q.front(); q.pop_front(); for (E e : g[node]) { if (d[e.to] == -1) { d[e.to] = d[node] + e.w; if (e.w) q.push_back(e.to); else q.push_front(e.to); } } } cout << d[getId(ex, ey, 0, 0)]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...