# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80327 | 2018-10-20T06:57:23 Z | xiaowuc1 | Tracks in the Snow (BOI13_tracks) | C++14 | 773 ms | 308440 KB |
#include <bits/stdc++.h> /* unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count(); mt19937 g1.seed(seed1); ios_base::sync_with_stdio(false); cin.tie(NULL); */ using namespace std; const double PI = 2 * acos(0); typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<vector<ll>> matrix; int r, c; char g[4005][4005]; int dp[4005][4005]; pii q[4005*4005*2]; int dx[4]{-1, 1, 0, 0}; int dy[4]{0, 0, -1, 1}; int main() { scanf("%d%d\n", &r, &c); for(int i = 0; i < r; i++) { scanf("%s", g[i]); for(int j = 0; j < c; j++) { dp[i][j] = 1 << 25; } } dp[0][0] = 1; int ql = 4005*4005; int qr = 4005*4005; q[qr++] = {0, 0}; int ret = 1; while(ql < qr) { pii curr = q[ql++]; ret = dp[curr.first][curr.second]; for(int k = 0; k < 4; k++) { int nx = curr.first + dx[k]; int ny = curr.second + dy[k]; if(nx < 0 || nx >= r || ny < 0 || ny >= c || g[nx][ny] == '.') continue; int nd = ret; if(g[nx][ny] != g[curr.first][curr.second]) { nd++; } if(nd < dp[nx][ny]) { dp[nx][ny] = nd; if(ret == nd) q[--ql] = {nx, ny}; else q[qr++] = {nx, ny}; } } } printf("%d\n", ret); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 6580 KB | Output is correct |
2 | Correct | 2 ms | 6580 KB | Output is correct |
3 | Correct | 2 ms | 6580 KB | Output is correct |
4 | Correct | 12 ms | 6580 KB | Output is correct |
5 | Correct | 6 ms | 6580 KB | Output is correct |
6 | Correct | 3 ms | 6580 KB | Output is correct |
7 | Correct | 3 ms | 6580 KB | Output is correct |
8 | Correct | 2 ms | 6580 KB | Output is correct |
9 | Correct | 3 ms | 6580 KB | Output is correct |
10 | Correct | 5 ms | 6580 KB | Output is correct |
11 | Correct | 5 ms | 6580 KB | Output is correct |
12 | Correct | 10 ms | 6580 KB | Output is correct |
13 | Correct | 6 ms | 6580 KB | Output is correct |
14 | Correct | 6 ms | 6580 KB | Output is correct |
15 | Correct | 16 ms | 7684 KB | Output is correct |
16 | Correct | 21 ms | 7864 KB | Output is correct |
17 | Correct | 13 ms | 7864 KB | Output is correct |
18 | Correct | 11 ms | 7864 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 33192 KB | Output is correct |
2 | Correct | 61 ms | 33192 KB | Output is correct |
3 | Correct | 327 ms | 113268 KB | Output is correct |
4 | Correct | 97 ms | 113268 KB | Output is correct |
5 | Correct | 179 ms | 126312 KB | Output is correct |
6 | Correct | 732 ms | 148096 KB | Output is correct |
7 | Correct | 26 ms | 148096 KB | Output is correct |
8 | Correct | 25 ms | 148096 KB | Output is correct |
9 | Correct | 4 ms | 148096 KB | Output is correct |
10 | Correct | 3 ms | 148096 KB | Output is correct |
11 | Correct | 27 ms | 148096 KB | Output is correct |
12 | Correct | 4 ms | 148096 KB | Output is correct |
13 | Correct | 55 ms | 148096 KB | Output is correct |
14 | Correct | 35 ms | 148096 KB | Output is correct |
15 | Correct | 34 ms | 148096 KB | Output is correct |
16 | Correct | 28 ms | 148096 KB | Output is correct |
17 | Correct | 136 ms | 148096 KB | Output is correct |
18 | Correct | 105 ms | 148096 KB | Output is correct |
19 | Correct | 89 ms | 148096 KB | Output is correct |
20 | Correct | 73 ms | 148096 KB | Output is correct |
21 | Correct | 191 ms | 148096 KB | Output is correct |
22 | Correct | 172 ms | 179212 KB | Output is correct |
23 | Correct | 291 ms | 179212 KB | Output is correct |
24 | Correct | 177 ms | 179212 KB | Output is correct |
25 | Correct | 402 ms | 213592 KB | Output is correct |
26 | Correct | 413 ms | 244940 KB | Output is correct |
27 | Correct | 493 ms | 244940 KB | Output is correct |
28 | Correct | 773 ms | 259792 KB | Output is correct |
29 | Correct | 703 ms | 274956 KB | Output is correct |
30 | Correct | 617 ms | 286028 KB | Output is correct |
31 | Correct | 713 ms | 302168 KB | Output is correct |
32 | Correct | 425 ms | 308440 KB | Output is correct |