/*
Author: Nguyen Tan Bao
Status:
Idea:
*/
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
const ll MODBASE = 1000000007LL;
const int MAXN = 510;
const int MAXM = 110;
const int MAXK = 16;
const int MAXQ = 200010;
// int d[210][210][3];
// III trace[210][210][3];
// queue<III> q;
int N, M;
vector<II> a[MAXN];
ll d[MAXN][MAXM];
ll sameLine(int x, int m) {
return min(x + 2, m+1 - x + 4);
}
ll check(int x, int y, int m) {
if (x == 0 && y == 0) return 0;
if (x == m+1 && y == m+1) return 4;
if (x == m+1 && y == 0) return 2;
if (y == m+1 && x == 0) return 2;
if (x == 0 || x == m+1) return sameLine(y, m);
// if (y == 0 || y == m+1)
return sameLine(x, m);
}
void goCloser(int &x, ll &res, int m) {
if (x % (m+1)) {
res += 2 * (x / (m+1));
x %= (m+1);
}
else {
if (x) {
res += 2 * (x / (m+1) - 1);
x = m+1;
}
}
}
ll solve(int x, int y, int m) {
x = abs(x); y = abs(y);
ll res = 0;
goCloser(x, res, m);
goCloser(y, res, m);
return res + check(x, y, m);
}
ll dist(int x, int y, int u, int v, int m) {
x -= u;
y -= v;
x = abs(x); y = abs(y);
if (m == 1) return x + y;
if (x % (m+1) == 0 || y % (m+1) == 0) return solve(x, y, m);
ll res = 1e18;
u = x % (m+1); v = y % (m+1);
res = min(res, u + 2 + solve(x-u, y, m));
res = min(res, u + 2 + solve(x-u, y-(m+1), m));
res = min(res, u + 2 + solve(x-u, y+(m+1), m));
res = min(res, v + 2 + solve(x, y-v, m));
res = min(res, v + 2 + solve(x-(m+1), y-v, m));
res = min(res, v + 2 + solve(x+(m+1), y-v, m));
u = m+1 - u; v = m+1 - v;
res = min(res, u + 2 + solve(x+u, y, m));
res = min(res, u + 2 + solve(x+u, y-(m+1), m));
res = min(res, u + 2 + solve(x+u, y+(m+1), m));
res = min(res, v + 2 + solve(x, y+v, m));
res = min(res, v + 2 + solve(x-(m+1), y+v, m));
res = min(res, v + 2 + solve(x+(m+1), y+v, m));
return res;
}
// void check(int x, int y, int c, int u, int v, int p) {
// if (x < 0 || x > 200 || y < 0 || y > 200) return;
// if (d[x][y][c] > d[u][v][p] + 1) {
// d[x][y][c] = d[u][v][p] + 1;
// trace[x][y][c] = III(II(u, v), p);
// q.push(III(II(x, y), c));
// }
// }
// void getTrace(III z) {
// cout << z.FI.FI << ' ' << z.FI.SE << ' ' << z.SE << endl;
// }
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
// FOR(i,0,200)
// FOR(j,0,200)
// FOR(k,0,2) d[i][j][k] = 1000000000;
// d[100][100][0] = 0;
// q.push(III(II(100,100), 0));
// int m = 5;
// while (!q.empty()) {
// III r = q.front(); q.pop();
// int x = r.FI.FI, y = r.FI.SE, c = r.SE;
// if (c == 0) {
// check(x+1, y, 2, x, y, c);
// check(x-m, y, 2, x, y, c);
// check(x, y+1, 1, x, y, c);
// check(x, y-m, 1, x, y, c);
// }
// else if (c == 1) {
// check(x+1, y, 1, x, y, c);
// check(x-1, y, 1, x, y, c);
// check(x, y-1, 0, x, y, c);
// check(x, y+m, 0, x, y, c);
// }
// else {
// check(x, y+1, 2, x, y, c);
// check(x, y-1, 2, x, y, c);
// check(x-1, y, 0, x, y, c);
// check(x+m, y, 0, x, y, c);
// }
// }
// FOR(i,91,110) {
// FOR(j,91,110) {
// if (d[i][j][0] >= 10) cout << "- ";
// else cout << d[i][j][0] << ' ';
// }
// cout << "\n";
// }
// cout << "\n";
// FOR(i,91,110) {
// FOR(j,91,110) {
// if (dist(100, 100, i, j, m) >= 10) cout << "- ";
// else cout << dist(100, 100, i, j, m) << " ";
// }
// cout << "\n";
// }
// getTrace(trace[106][100][1]);
int x, y;
cin >> N >> M;
cin >> x >> y;
a[0].push_back(II(x, y));
cin >> x >> y;
a[N].push_back(II(x, y));
FOR(i,1,N-1) {
int k;
cin >> k;
while (k--) {
cin >> x >> y;
a[i].push_back(II(x, y));
}
}
FOR(i,0,505) FOR(j,0,100) d[i][j] = 1e18;
d[0][0] = 0;
FOR(i,1,N)
FOR(j,0,SZ(a[i-1])-1)
FOR(k,0,SZ(a[i])-1) d[i][k] = min(d[i][k], d[i-1][j] + dist(a[i-1][j].FI, a[i-1][j].SE, a[i][k].FI, a[i][k].SE, M));
cout << d[N][0];
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
768 KB |
Output is correct |
| 2 |
Correct |
5 ms |
768 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
896 KB |
Output is correct |
| 5 |
Correct |
5 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
768 KB |
Output is correct |
| 2 |
Correct |
7 ms |
768 KB |
Output is correct |
| 3 |
Correct |
8 ms |
768 KB |
Output is correct |
| 4 |
Correct |
9 ms |
768 KB |
Output is correct |
| 5 |
Correct |
6 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
172 ms |
1328 KB |
Output is correct |
| 2 |
Correct |
188 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
182 ms |
1316 KB |
Output is correct |
| 4 |
Correct |
191 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
197 ms |
1280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
269 ms |
1648 KB |
Output is correct |
| 2 |
Correct |
257 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
248 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
282 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
258 ms |
1656 KB |
Output is correct |
