# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
535449 | 2022-03-10T09:43:35 Z | dozer | Tracks in the Snow (BOI13_tracks) | C++14 | 322 ms | 548448 KB |
#include <bits/stdc++.h> using namespace std; #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); #define fastio() ios_base::sync_with_stdio(0), cin.tie(0); #define pb push_back #define ll long long #define sp " " #define endl "\n" #define modulo 100000007 #define N 20000005 #define st first #define nd second //#define int long long #define pii pair<int, int> vector<int> adj[N]; int id[5015][5015], arr[5015][5015], col[N], dist[N]; unordered_map<char, int> value; int32_t main() { fastio(); #ifndef ONLINE_JUDGE fileio(); #endif //cout<<(((4005 * 4005 * 2) + 6 * N) * 4)/ (1<<20)<<endl; int h, w; cin>>h>>w; value['F'] = 1, value['R'] = 2, value['.'] = 3; int ctr = 1; for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { char tmp; cin>>tmp; /* switch(tmp) { case 'F': arr[i][j] = 1; break; case 'R': arr[i][j] = 2; break; case '.': arr[i][j] = 3; break; } */ arr[i][j] = value[tmp]; id[i][j] = ctr; col[id[i][j]] = arr[i][j]; ctr++; } } for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { if (arr[i][j] == 3) continue; int color = arr[i][j]; if (i < h && arr[i + 1][j] != 3) { adj[id[i][j]].pb(id[i + 1][j]); adj[id[i + 1][j]].pb(id[i][j]); } if (j < w && arr[i][j + 1] != 3) { adj[id[i][j]].pb(id[i][j + 1]); adj[id[i][j + 1]].pb(id[i][j]); } } } int color = col[1], ans = 0; deque<int> q; memset(dist, modulo, sizeof(dist)); q.push_front(1); dist[1] = 1; int steps = 0; while(!q.empty()) { steps++; int top = q.front(); q.pop_front(); ans = max(ans, dist[top]); for (int k = 0; k < adj[top].size(); k++) { int curr = adj[top][k]; int d = ((col[top] == col[curr]) ? 0 : 1); if (d == 0 && dist[curr] > dist[top]) { dist[curr] = dist[top]; q.push_front(curr); } else if (dist[curr] > dist[top] + 1) { dist[curr] = dist[top] + 1; q.push_back(curr); } } } //cout<<steps<<endl; cout<<ans<<endl; //cerr<<"time taken : "<<(float) clock() / CLOCKS_PER_SEC<<" seconds\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 313 ms | 548288 KB | Output isn't correct |
2 | Incorrect | 242 ms | 548224 KB | Output isn't correct |
3 | Incorrect | 257 ms | 548332 KB | Output isn't correct |
4 | Incorrect | 278 ms | 548220 KB | Output isn't correct |
5 | Incorrect | 262 ms | 548328 KB | Output isn't correct |
6 | Incorrect | 264 ms | 548260 KB | Output isn't correct |
7 | Incorrect | 258 ms | 548328 KB | Output isn't correct |
8 | Incorrect | 270 ms | 548320 KB | Output isn't correct |
9 | Incorrect | 268 ms | 548448 KB | Output isn't correct |
10 | Incorrect | 278 ms | 548256 KB | Output isn't correct |
11 | Incorrect | 267 ms | 548300 KB | Output isn't correct |
12 | Incorrect | 249 ms | 548212 KB | Output isn't correct |
13 | Incorrect | 290 ms | 548300 KB | Output isn't correct |
14 | Incorrect | 255 ms | 548284 KB | Output isn't correct |
15 | Incorrect | 263 ms | 548332 KB | Output isn't correct |
16 | Incorrect | 244 ms | 548272 KB | Output isn't correct |
17 | Incorrect | 255 ms | 548448 KB | Output isn't correct |
18 | Incorrect | 254 ms | 548292 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 265 ms | 548220 KB | Output isn't correct |
2 | Incorrect | 272 ms | 548360 KB | Output isn't correct |
3 | Incorrect | 243 ms | 548320 KB | Output isn't correct |
4 | Incorrect | 289 ms | 548224 KB | Output isn't correct |
5 | Incorrect | 254 ms | 548300 KB | Output isn't correct |
6 | Incorrect | 252 ms | 548216 KB | Output isn't correct |
7 | Incorrect | 288 ms | 548228 KB | Output isn't correct |
8 | Incorrect | 249 ms | 548324 KB | Output isn't correct |
9 | Incorrect | 288 ms | 548304 KB | Output isn't correct |
10 | Incorrect | 273 ms | 548228 KB | Output isn't correct |
11 | Incorrect | 263 ms | 548272 KB | Output isn't correct |
12 | Incorrect | 289 ms | 548444 KB | Output isn't correct |
13 | Incorrect | 271 ms | 548300 KB | Output isn't correct |
14 | Incorrect | 289 ms | 548228 KB | Output isn't correct |
15 | Incorrect | 266 ms | 548288 KB | Output isn't correct |
16 | Incorrect | 266 ms | 548304 KB | Output isn't correct |
17 | Incorrect | 309 ms | 548324 KB | Output isn't correct |
18 | Incorrect | 300 ms | 548328 KB | Output isn't correct |
19 | Incorrect | 271 ms | 548324 KB | Output isn't correct |
20 | Incorrect | 294 ms | 548216 KB | Output isn't correct |
21 | Incorrect | 309 ms | 548216 KB | Output isn't correct |
22 | Incorrect | 287 ms | 548232 KB | Output isn't correct |
23 | Incorrect | 297 ms | 548312 KB | Output isn't correct |
24 | Incorrect | 285 ms | 548264 KB | Output isn't correct |
25 | Incorrect | 274 ms | 548328 KB | Output isn't correct |
26 | Incorrect | 322 ms | 548320 KB | Output isn't correct |
27 | Incorrect | 295 ms | 548276 KB | Output isn't correct |
28 | Incorrect | 322 ms | 548204 KB | Output isn't correct |
29 | Incorrect | 262 ms | 548272 KB | Output isn't correct |
30 | Incorrect | 269 ms | 548232 KB | Output isn't correct |
31 | Incorrect | 270 ms | 548320 KB | Output isn't correct |
32 | Incorrect | 286 ms | 548328 KB | Output isn't correct |