oj.uz

Submission #867727

# Submission time Handle Problem Language Result Execution time Memory
867727 2023-10-29T10:24:06 Z BoopyTheNoob Tracks in the Snow (BOI13_tracks) C++14
40.2083 / 100
 2000 ms 758216 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));
    int dist[4000][4000];
    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
18.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 64336 KB Output is correct
2 Incorrect 30 ms 63068 KB Output isn't correct
3 Incorrect 30 ms 63068 KB Output isn't correct
4 Correct 49 ms 66376 KB Output is correct
5 Incorrect 32 ms 63060 KB Output isn't correct
6 Incorrect 31 ms 63028 KB Output isn't correct
7 Incorrect 30 ms 63060 KB Output isn't correct
8 Correct 32 ms 63192 KB Output is correct
9 Correct 32 ms 63108 KB Output is correct
10 Correct 32 ms 63056 KB Output is correct
11 Correct 37 ms 63924 KB Output is correct
12 Correct 43 ms 63832 KB Output is correct
13 Incorrect 32 ms 63068 KB Output isn't correct
14 Incorrect 32 ms 63068 KB Output isn't correct
15 Correct 57 ms 63872 KB Output is correct
16 Correct 71 ms 64576 KB Output is correct
17 Correct 46 ms 63580 KB Output is correct
18 Correct 48 ms 66272 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63068 KB Output is correct
2 Incorrect 110 ms 64840 KB Output isn't correct
3 Incorrect 57 ms 80836 KB Output isn't correct
4 Correct 98 ms 67184 KB Output is correct
5 Correct 210 ms 72796 KB Output is correct
6 Execution timed out 2051 ms 296628 KB Time limit exceeded
7 Incorrect 31 ms 63192 KB Output isn't correct
8 Correct 31 ms 63056 KB Output is correct
9 Incorrect 34 ms 63012 KB Output isn't correct
10 Incorrect 30 ms 63060 KB Output isn't correct
11 Correct 31 ms 63060 KB Output is correct
12 Incorrect 30 ms 63064 KB Output isn't correct
13 Incorrect 126 ms 65060 KB Output isn't correct
14 Incorrect 73 ms 64316 KB Output isn't correct
15 Correct 44 ms 64224 KB Output is correct
16 Incorrect 77 ms 64080 KB Output isn't correct
17 Incorrect 36 ms 67412 KB Output isn't correct
18 Correct 111 ms 67420 KB Output is correct
19 Correct 96 ms 67208 KB Output is correct
20 Incorrect 36 ms 66644 KB Output isn't correct
21 Incorrect 52 ms 73296 KB Output isn't correct
22 Correct 250 ms 72788 KB Output is correct
23 Incorrect 443 ms 72016 KB Output isn't correct
24 Incorrect 45 ms 72796 KB Output isn't correct
25 Incorrect 59 ms 80724 KB Output isn't correct
26 Execution timed out 2098 ms 758216 KB Time limit exceeded
27 Execution timed out 2044 ms 383076 KB Time limit exceeded
28 Execution timed out 2065 ms 298264 KB Time limit exceeded
29 Execution timed out 2079 ms 279080 KB Time limit exceeded
30 Execution timed out 2075 ms 329716 KB Time limit exceeded
31 Correct 1795 ms 82136 KB Output is correct
32 Execution timed out 2057 ms 349768 KB Time limit exceeded