Submission #155963

#TimeUsernameProblemLanguageResultExecution timeMemory
155963MinnakhmetovOBELISK (NOI14_obelisk)C++14
0 / 25
10 ms5496 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 N = 11, M = 1e5, INF = 1e9; vector<pair<int, int>> v[N]; vector<E> g[M]; int s[N]; ll d[M]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int m, k, sx, sy, ex, ey; cin >> m >> k >> sx >> sy >> ex >> ey; v[k].push_back({sx, sy}); v[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; v[i].push_back({x, y}); } } for (int i = 0; i < k; i++) { s[i + 1] = s[i] + v[i].size(); } for (int i = k; i > 0; i--) { for (int x = 0; x < v[i].size(); x++) { for (int y = 0; y < v[i - 1].size(); y++) { int d = abs(v[i][x].first - v[i - 1][y].first) + abs(v[i][x].second - v[i - 1][y].second); g[x + s[i]].push_back({y + s[i - 1], d}); } } } // for (int i = 0; i < M; i++) { // for (E e : g[i]) { // cout << i + 1 << " " << e.to + 1 << " " << e.w << "\n"; // } // } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; fill(d, d + M, INF); d[s[k]] = 0; q.push({0, s[k]}); while (!q.empty()) { auto p = q.top(); q.pop(); if (p.first > d[p.second]) continue; int node = p.second; for (E e : g[node]) { if (d[e.to] > d[node] + e.w) { d[e.to] = d[node] + e.w; q.push({d[e.to], e.to}); } } } cout << d[0] << "\n"; return 0; }

Compilation message (stderr)

obelisk.cpp: In function 'int main()':
obelisk.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int x = 0; x < v[i].size(); x++) {
                         ~~^~~~~~~~~~~~~
obelisk.cpp:45:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int y = 0; y < v[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...