oj.uz

답안 #867716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867716 2023-10-29T10:04:33 Z BoopyTheNoob Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 755100 KB 
#include <bits/stdc++.h>
using namespace std;

int main (void) {
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 3164 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 21 ms 4444 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 6 ms 1372 KB Output is correct
12 Correct 14 ms 1596 KB Output is correct
13 Correct 4 ms 860 KB Output is correct
14 Correct 4 ms 860 KB Output is correct
15 Correct 28 ms 2392 KB Output is correct
16 Correct 38 ms 3164 KB Output is correct
17 Correct 17 ms 2136 KB Output is correct
18 Correct 22 ms 4504 KB Output is correct

Subtask #2
54.6875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 100 ms 10564 KB Output is correct
3 Correct 574 ms 109184 KB Output is correct
4 Correct 122 ms 25976 KB Output is correct
5 Correct 300 ms 55892 KB Output is correct
6 Execution timed out 2035 ms 324648 KB Time limit exceeded
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 5 ms 1116 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 452 KB Output is correct
13 Correct 106 ms 10756 KB Output is correct
14 Correct 60 ms 6792 KB Output is correct
15 Correct 29 ms 7256 KB Output is correct
16 Correct 57 ms 4584 KB Output is correct
17 Correct 284 ms 28240 KB Output is correct
18 Correct 131 ms 27676 KB Output is correct
19 Correct 134 ms 25944 KB Output is correct
20 Correct 131 ms 23996 KB Output is correct
21 Correct 326 ms 57816 KB Output is correct
22 Correct 296 ms 55892 KB Output is correct
23 Correct 515 ms 48580 KB Output is correct
24 Correct 265 ms 56840 KB Output is correct
25 Correct 595 ms 108576 KB Output is correct
26 Execution timed out 2092 ms 755100 KB Time limit exceeded
27 Execution timed out 2081 ms 409792 KB Time limit exceeded
28 Execution timed out 2106 ms 326616 KB Time limit exceeded
29 Execution timed out 2053 ms 307672 KB Time limit exceeded
30 Execution timed out 2053 ms 356216 KB Time limit exceeded
31 Correct 1867 ms 70740 KB Output is correct
32 Execution timed out 2067 ms 377868 KB Time limit exceeded