Submission #156020

#TimeUsernameProblemLanguageResultExecution timeMemory
156020MinnakhmetovOBELISK (NOI14_obelisk)C++14
25 / 25
395 ms63512 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 = 505, H = 105, N = K * H, C = 805, Z = 402, INF = 1e9, M = C * C * 3; vector<pair<int, int>> holes[K]; vector<E> g[M], g2[N]; int d[M], s[K], d2[N], anc[M], dx[3] = {-1, 1, 0}; int m, k, sx, sy, ex, ey; int getId(int x, int y, int z) { return 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}); } int calc(int x, int y) { if (m == 1) return abs(x) + abs(y); int ans = INF; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int g = 0; g < 2; g++) { for (int h = 0; h < 2; h++) { int p = abs(x + dx[i] * (m + 1)), q = abs(y + dx[j] * (m + 1)), t1 = p / (m + 1) + (i < 2), t2 = q / (m + 1) + (j < 2), cur = t1 * 2 + t2 * 2 + g * 2 + h * 2; p %= (m + 1); q %= (m + 1); if (p) { if (!t2) cur += 2; if (g) cur += m + 1 - p; else cur += p; } if (q) { if (!t1) cur += 2; if (h) cur += m + 1 - q; else cur += q; } ans = min(ans, cur); } } } } return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> k >> m >> sx >> sy >> ex >> ey; // for (int x = 0; x < C; x++) { // for (int y = 0; y < C; y++) { // if (m == 1) { // addEdge(getId(x, y, 0), getId(x, y, 1), 0); // addEdge(getId(x, y, 1), getId(x, y, 2), 0); // } // if (x + 1 < C) { // addEdge(getId(x, y, 0), getId(x + 1, y, 1), 1); // addEdge(getId(x, y, 2), getId(x + 1, y, 2), 1); // } // if (y + 1 < C) { // addEdge(getId(x, y, 0), getId(x, y + 1, 2), 1); // addEdge(getId(x, y, 1), getId(x, y + 1, 1), 1); // } // if (x + m < C) { // addEdge(getId(x, y, 1), getId(x + m, y, 0), 1); // } // if (y + m < C) { // addEdge(getId(x, y, 2), getId(x, y + m, 0), 1); // } // } // } // fill(d, d + M, -1); // fill(anc, anc + M, -1); // int start = getId(Z, Z, 0); // 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; // anc[e.to] = node; // if (e.w) // q.push_back(e.to); // else // q.push_front(e.to); // } // } // } // cout << calc(0, 3); // return 0; // for (int i = 0; i <= 15; i++) { // for (int j = 0; j <= 15; j++) { // int cur = d[getId(Z + i, Z + j, 0)] ; // if (cur < 10) // cout << " "; // cout << cur<< "/"; // int cur2 = calc(i, j); // if (cur2 < 10) // cout << " "; // cout << cur2 << " "; // if (cur != cur2) { // cout <<"!"; // exit(1); // } // } // cout << "\n"; // } // pr(getId(2 + Z, 2 + Z, 0)); // return 0; // cout << d[getId(Z + 1, Z + 1, 0)]; // return 0; holes[k].push_back({sx, sy}); holes[0].push_back({ex, ey}); for (int i = k - 1; i > 0; i--) { int h; cin >> h; while (h--) { int x, y; cin >> x >> y; holes[i].push_back({x, y}); } } for (int i = 0; i < k; i++) { s[i + 1] = s[i] + holes[i].size(); } for (int i = 1; i <= k; i++) { for (int x = 0; x < holes[i].size(); x++) { for (int y = 0; y < holes[i - 1].size(); y++) { int dist = calc(holes[i - 1][y].first - holes[i][x].first, holes[i - 1][y].second - holes[i][x].second); // cout << x + s[i] << " " << y + s[i - 1] << "\n"; g2[x + s[i]].push_back({y + s[i - 1], dist}); } } } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; fill(d2, d2 + N, INF); d2[s[k]] = 0; pq.push({0, s[k]}); while (!pq.empty()) { auto p = pq.top(); pq.pop(); if (p.first > d2[p.second]) continue; int node = p.second; for (E e : g2[node]) { if (d2[e.to] > d2[node] + e.w) { d2[e.to] = d2[node] + e.w; pq.push({d2[e.to], e.to}); } } } cout << d2[0] << "\n"; return 0; }

Compilation message (stderr)

obelisk.cpp: In function 'int main()':
obelisk.cpp:180:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int x = 0; x < holes[i].size(); x++) {
                         ~~^~~~~~~~~~~~~~~~~
obelisk.cpp:181:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int y = 0; y < holes[i - 1].size(); y++) {
                             ~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...