#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
// #define fisier 1
using namespace std;
typedef long long ll;
int k, m;
int sx, sy, ex, ey, sp[505];
int dx[3] = {-1, 1, 0};
vector<pair<int, int> >gauri[505], v[100002];
int calc(int x, int y)
{
if(m == 1)
return abs(x) + abs(y);
int ans = (1<<30);
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));
int q = abs(y + dx[j] * (m + 1));
int t1 = p / (m + 1) + (i < 2);
int t2 = q / (m + 1) + (j < 2);
int 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;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int di[502];
int main()
{
#ifdef fisier
ifstream f("input.in");
ofstream g("output.out");
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> m;
cin >> sx >> sy >> ex >> ey;
gauri[k].push_back({sx, sy});
gauri[0].push_back({ex, ey});
for(int i = k-1; i >= 1; --i)
{
int nr;
cin >> nr;
for(; nr; --nr)
{
int xa, ya;
cin >> xa >> ya;
gauri[i].pb({xa, ya});
}
}
for(int i = 0; i < k; ++i)
sp[i+1] = sp[i] + gauri[i].size();
for(int i = 1; i <= k; i++)
for(int x = 0; x < gauri[i].size(); x++)
for(int y = 0; y < gauri[i - 1].size(); y++)
{
int dist = calc(gauri[i - 1][y].fi - gauri[i][x].fi, gauri[i - 1][y].se - gauri[i][x].se);
v[x + sp[i]].push_back({y + sp[i - 1], dist});
}
for(int i = 0; i <= 500; ++i)
di[i] = (1<<30);
di[sp[k]] = 0;
pq.push({0, sp[k]});
while(!pq.empty())
{
pair<int, int> p = pq.top();
pq.pop();
if(p.fi > di[p.se])
continue;
int nod = p.se;
for(auto e : v[nod])
if(di[e.fi] > di[nod] + e.se)
{
di[e.fi] = di[nod] + e.se;
pq.push({di[e.fi], e.fi});
}
}
cout << di[0];
return 0;
}
Compilation message
obelisk.cpp: In function 'int main()':
obelisk.cpp:99:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x = 0; x < gauri[i].size(); x++)
~~^~~~~~~~~~~~~~~~~
obelisk.cpp:100:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int y = 0; y < gauri[i - 1].size(); y++)
~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2788 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3064 KB |
Output is correct |
| 2 |
Correct |
16 ms |
2936 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2936 KB |
Output is correct |
| 4 |
Runtime error |
16 ms |
6264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
198 ms |
16724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
211 ms |
18168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
