제출 #224686

#제출 시각아이디문제언어결과실행 시간메모리
224686farmerboy오벨리스크 (NOI14_obelisk)C++14
25 / 25
282 ms1664 KiB
/* 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...