oj.uz

Submission #867749

# Submission time Handle Problem Language Result Execution time Memory
867749 2023-10-29T12:14:33 Z BoopyTheNoob Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 391 ms 126736 KB 
#include <bits/stdc++.h>
using namespace std;

int main (void) {
    iostream::sync_with_stdio(false);
	cin.tie(0);
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int N, M;
    cin >> N >> M;
    //vector<string> grid(N);
    string grid[4000];
    for (int i = 0; i < N; i++)
        cin >> grid[i];
    //vector<vector<int>> dist(N, vector<int>(M, 0));
    int dist[4000][4000];
    deque<pair<int, int>> bfs;
    bfs.push_back({0, 0});
    dist[0][0] = 1;
    int ans = 1;
    while (!bfs.empty()) {
        int x = bfs.front().first, y = bfs.front().second;
        bfs.pop_front();
        ans = max(ans, dist[x][y]);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            if (dist[nx][ny] != 0 || grid[nx][ny] == '.')
                continue;
            pair<int, int> next = {nx, ny};
            if (grid[x][y] != grid[nx][ny]) {
                dist[nx][ny] = dist[x][y] + 1;
                bfs.push_back(next);
            } else {
                dist[nx][ny] = dist[x][y];
                bfs.push_front(next);
            }
        }
    }
    /*for (auto x: dist) {
        for (auto y: x) {
            cout << y << " ";
        }
        cout << endl;
    }*/
    cout << ans << endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63324 KB Output is correct
2 Correct 28 ms 63068 KB Output is correct
3 Correct 29 ms 63068 KB Output is correct
4 Correct 31 ms 63520 KB Output is correct
5 Correct 30 ms 63068 KB Output is correct
6 Correct 29 ms 63004 KB Output is correct
7 Correct 30 ms 63060 KB Output is correct
8 Correct 28 ms 63068 KB Output is correct
9 Correct 29 ms 63060 KB Output is correct
10 Correct 30 ms 63068 KB Output is correct
11 Correct 29 ms 63060 KB Output is correct
12 Correct 30 ms 63056 KB Output is correct
13 Correct 29 ms 63300 KB Output is correct
14 Correct 30 ms 63244 KB Output is correct
15 Correct 34 ms 63216 KB Output is correct
16 Correct 35 ms 63272 KB Output is correct
17 Correct 39 ms 63312 KB Output is correct
18 Correct 32 ms 63580 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63320 KB Output is correct
2 Correct 60 ms 65080 KB Output is correct
3 Correct 147 ms 80720 KB Output is correct
4 Correct 64 ms 67140 KB Output is correct
5 Correct 101 ms 72784 KB Output is correct
6 Correct 388 ms 93980 KB Output is correct
7 Correct 29 ms 63072 KB Output is correct
8 Correct 29 ms 63068 KB Output is correct
9 Correct 30 ms 63248 KB Output is correct
10 Correct 29 ms 63068 KB Output is correct
11 Correct 35 ms 63060 KB Output is correct
12 Correct 29 ms 63056 KB Output is correct
13 Correct 50 ms 64604 KB Output is correct
14 Correct 41 ms 64140 KB Output is correct
15 Correct 36 ms 64088 KB Output is correct
16 Correct 39 ms 63752 KB Output is correct
17 Correct 87 ms 67412 KB Output is correct
18 Correct 61 ms 67152 KB Output is correct
19 Correct 60 ms 66904 KB Output is correct
20 Correct 57 ms 66652 KB Output is correct
21 Correct 100 ms 73148 KB Output is correct
22 Correct 93 ms 72812 KB Output is correct
23 Correct 148 ms 71584 KB Output is correct
24 Correct 93 ms 72784 KB Output is correct
25 Incorrect 63 ms 80724 KB Output isn't correct
26 Correct 340 ms 126736 KB Output is correct
27 Correct 307 ms 99068 KB Output is correct
28 Correct 391 ms 94112 KB Output is correct
29 Correct 379 ms 91852 KB Output is correct
30 Correct 371 ms 97740 KB Output is correct
31 Correct 302 ms 74692 KB Output is correct
32 Correct 320 ms 97732 KB Output is correct