oj.uz

Submission #394172

# Submission time Handle Problem Language Result Execution time Memory
394172 2021-04-26T03:24:50 Z SirCovidThe19th Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1482 ms 122428 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	
    int h, w;
    cin >> h >> w;

    char grid[h][w];
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            cin >> grid[i][j];
    
    int ans = 0;
    int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1};
    int depth[h][w];
    deque<pair<int, int>> trav;

    memset(depth, 0, sizeof(depth));
    depth[0][0] = 1; trav.push_back({0, 0});

    while (!trav.empty()){
        pair<int, int> curr = trav.front(); trav.pop_front();
        ans = max(ans, depth[curr.first][curr.second]);
        for (int i = 0; i < 4; i++){
            int x = curr.first+dx[i]; int y = curr.second+dy[i];
            if (x < 0 or x >= h or y < 0 or y >= w or grid[x][y] == '.' or depth[x][y] != 0) continue;
            if (grid[x][y] == grid[curr.first][curr.second]){
                depth[x][y] = depth[curr.first][curr.second];
                trav.push_front({x, y});
            }
            else{
                depth[x][y] = depth[curr.first][curr.second]+1;
                trav.push_back({x, y});
            }
        }
    }
    cout<<ans<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1744 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 14 ms 1356 KB Output is correct
5 Correct 7 ms 696 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 9 ms 716 KB Output is correct
13 Correct 7 ms 720 KB Output is correct
14 Correct 7 ms 716 KB Output is correct
15 Correct 23 ms 1788 KB Output is correct
16 Correct 24 ms 1648 KB Output is correct
17 Correct 20 ms 1612 KB Output is correct
18 Correct 14 ms 1320 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 127 ms 9552 KB Output is correct
3 Correct 1105 ms 94076 KB Output is correct
4 Correct 265 ms 22208 KB Output is correct
5 Correct 652 ms 53036 KB Output is correct
6 Correct 1440 ms 108136 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 123 ms 9372 KB Output is correct
14 Correct 71 ms 5544 KB Output is correct
15 Correct 71 ms 6112 KB Output is correct
16 Correct 54 ms 4004 KB Output is correct
17 Correct 346 ms 24092 KB Output is correct
18 Correct 289 ms 23840 KB Output is correct
19 Correct 262 ms 22268 KB Output is correct
20 Correct 239 ms 20396 KB Output is correct
21 Correct 645 ms 55076 KB Output is correct
22 Correct 654 ms 53076 KB Output is correct
23 Correct 618 ms 45828 KB Output is correct
24 Correct 624 ms 53708 KB Output is correct
25 Correct 1348 ms 94396 KB Output is correct
26 Correct 1014 ms 122428 KB Output is correct
27 Correct 1331 ms 120868 KB Output is correct
28 Correct 1482 ms 107812 KB Output is correct
29 Correct 1468 ms 106348 KB Output is correct
30 Correct 1411 ms 110132 KB Output is correct
31 Correct 1064 ms 61000 KB Output is correct
32 Correct 1289 ms 109448 KB Output is correct