oj.uz

Submission #867725

# Submission time Handle Problem Language Result Execution time Memory
867725 2023-10-29T10:22:46 Z BoopyTheNoob Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 749996 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);
    string grid[4000];
    for (int i = 0; i < N; i++)
        cin >> grid[i];
    vector<vector<int>> dist(N, vector<int>(M, 0));
    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] != 0 || 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 35 ms 2908 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 20 ms 4444 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 3 ms 908 KB Output is correct
11 Correct 6 ms 1628 KB Output is correct
12 Correct 12 ms 1628 KB Output is correct
13 Correct 3 ms 1100 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 26 ms 2524 KB Output is correct
16 Correct 35 ms 2904 KB Output is correct
17 Correct 14 ms 2200 KB Output is correct
18 Correct 19 ms 4496 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 81 ms 9704 KB Output is correct
3 Correct 373 ms 89932 KB Output is correct
4 Correct 72 ms 21868 KB Output is correct
5 Correct 239 ms 50664 KB Output is correct
6 Execution timed out 2101 ms 306744 KB Time limit exceeded
7 Correct 1 ms 844 KB Output is correct
8 Correct 2 ms 860 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 884 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 81 ms 9868 KB Output is correct
14 Correct 45 ms 5888 KB Output is correct
15 Correct 21 ms 6292 KB Output is correct
16 Correct 46 ms 4640 KB Output is correct
17 Correct 238 ms 23420 KB Output is correct
18 Correct 86 ms 22832 KB Output is correct
19 Correct 83 ms 21644 KB Output is correct
20 Correct 87 ms 19804 KB Output is correct
21 Correct 213 ms 52304 KB Output is correct
22 Correct 209 ms 50500 KB Output is correct
23 Correct 435 ms 44112 KB Output is correct
24 Correct 165 ms 50884 KB Output is correct
25 Correct 466 ms 89208 KB Output is correct
26 Execution timed out 2070 ms 749996 KB Time limit exceeded
27 Execution timed out 2078 ms 381320 KB Time limit exceeded
28 Execution timed out 2027 ms 296360 KB Time limit exceeded
29 Execution timed out 2064 ms 279292 KB Time limit exceeded
30 Execution timed out 2070 ms 328496 KB Time limit exceeded
31 Correct 1878 ms 59884 KB Output is correct
32 Execution timed out 2065 ms 349872 KB Time limit exceeded