oj.uz

Submission #867717

# Submission time Handle Problem Language Result Execution time Memory
867717 2023-10-29T10:06:41 Z BoopyTheNoob Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 743992 KB 
#include <iostream>
#include <vector>
#include <deque>
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);
    for (int i = 0; i < N; i++)
        cin >> grid[i];
    vector<vector<int>> dist(N, vector<int>(M, 1e9));
    deque<vector<int>> bfs;
    bfs.push_back({0, 0, 1});
    int ans = 0;
    while (!bfs.empty()) {
        int x = bfs.front()[0], y = bfs.front()[1], d = bfs.front()[2];
        bfs.pop_front();
        dist[x][y] = d;
        ans = max(ans, d);
        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] < 1e9 || grid[nx][ny] == '.')
                continue;
            vector<int> next = {nx, ny, d};
            if (grid[x][y] != grid[nx][ny]) {
                next[2]++;
                bfs.push_back(next);
            } else
                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 2908 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 19 ms 4444 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 3 ms 908 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 13 ms 1576 KB Output is correct
13 Correct 3 ms 856 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 25 ms 2396 KB Output is correct
16 Correct 34 ms 2904 KB Output is correct
17 Correct 14 ms 1880 KB Output is correct
18 Correct 19 ms 4444 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 97 ms 9552 KB Output is correct
3 Correct 361 ms 89292 KB Output is correct
4 Correct 69 ms 21324 KB Output is correct
5 Correct 186 ms 50220 KB Output is correct
6 Execution timed out 2073 ms 304776 KB Time limit exceeded
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 87 ms 9532 KB Output is correct
14 Correct 45 ms 5724 KB Output is correct
15 Correct 17 ms 6236 KB Output is correct
16 Correct 45 ms 4188 KB Output is correct
17 Correct 203 ms 23388 KB Output is correct
18 Correct 86 ms 22764 KB Output is correct
19 Correct 69 ms 21336 KB Output is correct
20 Correct 84 ms 19548 KB Output is correct
21 Correct 220 ms 52040 KB Output is correct
22 Correct 185 ms 50312 KB Output is correct
23 Correct 464 ms 43860 KB Output is correct
24 Correct 157 ms 50604 KB Output is correct
25 Correct 402 ms 89468 KB Output is correct
26 Execution timed out 2086 ms 743992 KB Time limit exceeded
27 Execution timed out 2085 ms 383500 KB Time limit exceeded
28 Execution timed out 2076 ms 298292 KB Time limit exceeded
29 Execution timed out 2087 ms 279776 KB Time limit exceeded
30 Execution timed out 2076 ms 328420 KB Time limit exceeded
31 Correct 1729 ms 59716 KB Output is correct
32 Execution timed out 2065 ms 350068 KB Time limit exceeded