#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const int MAX_M = 1e5 + 1;
const int MAX_K = 5e2 + 1;
const int MAX_H = 1e2 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int dx[] = {-1, 1, 0};
int m, k, psz[MAX_K];
ar<int,2> s, e;
vector<ar<int,2>> holes[MAX_K], adj[MAX_K * MAX_H];
vector<int> dist;
int calc(int x, int y) {
if (m == 1) return abs(x) + abs(y);
int res = 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;
}
res = min(res, cur);
}
}
}
}
return res;
}
void dijk(int s) {
dist.assign(MAX_K * MAX_M, INF);
priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;
dist[s] = 0; pq.push({0, s});
while (pq.size()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
void solve() {
cin >> k >> m >> s[0] >> s[1] >> e[0] >> e[1];
holes[k].push_back(s);
holes[0].push_back(e);
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++) {
psz[i + 1] = psz[i] + holes[i].size();
}
for (int i = 1; i <= k; i++) {
for (int u = 0; u < holes[i].size(); u++) {
for (int v = 0; v < holes[i - 1].size(); v++) {
int dist = calc(holes[i - 1][v][0] - holes[i][u][0], holes[i - 1][v][1] - holes[i][u][1]);
adj[u + psz[i]].push_back({v + psz[i - 1], dist});
}
}
}
dijk(psz[k]);
cout << dist[0] << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc = 1;
// cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
Compilation message
obelisk.cpp: In function 'void solve()':
obelisk.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int u = 0; u < holes[i].size(); u++) {
| ~~^~~~~~~~~~~~~~~~~
obelisk.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int v = 0; v < holes[i - 1].size(); v++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
197612 KB |
Output is correct |
| 2 |
Correct |
114 ms |
197612 KB |
Output is correct |
| 3 |
Correct |
116 ms |
197612 KB |
Output is correct |
| 4 |
Correct |
118 ms |
197612 KB |
Output is correct |
| 5 |
Correct |
123 ms |
197668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
197740 KB |
Output is correct |
| 2 |
Correct |
124 ms |
197868 KB |
Output is correct |
| 3 |
Correct |
121 ms |
197868 KB |
Output is correct |
| 4 |
Correct |
124 ms |
198124 KB |
Output is correct |
| 5 |
Correct |
122 ms |
197740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
211692 KB |
Output is correct |
| 2 |
Correct |
386 ms |
213356 KB |
Output is correct |
| 3 |
Correct |
388 ms |
212588 KB |
Output is correct |
| 4 |
Correct |
408 ms |
213216 KB |
Output is correct |
| 5 |
Correct |
396 ms |
213808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
213148 KB |
Output is correct |
| 2 |
Correct |
403 ms |
212332 KB |
Output is correct |
| 3 |
Correct |
408 ms |
212716 KB |
Output is correct |
| 4 |
Correct |
432 ms |
214252 KB |
Output is correct |
| 5 |
Correct |
408 ms |
212972 KB |
Output is correct |
