oj.uz

Submission #134080

# Submission time Handle Problem Language Result Execution time Memory
134080 2019-07-22T04:05:13 Z fredbr Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1452 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

int const maxn = 4010;

int cnt = 0;
int n, m;
char vis[maxn][maxn];
char v[maxn][maxn];

using ii = pair<int, int>;

vector<ii> nxt;

void dfs(int x, int y) {
    static int const dx[] = {0, 1, 0, -1};
    static int const dy[] = {1, 0, -1, 0};

    if (vis[x][y]) return;
    if (v[x][y] == '.') return;

    vis[x][y] = 1;
    cnt--;

    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (xx >= 0 and xx < n and yy >= 0 and yy < m) {
            if (vis[xx][yy]) continue;

            if (v[xx][yy] == v[x][y]) dfs(xx, yy);
            else if (v[xx][yy] != '.') {
                nxt.emplace_back(xx, yy);
            }
        }
    }
    v[x][y] = '.';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
            if (v[i][j] != '.') cnt++;
        }
    }

    int ans = 0;
    nxt.emplace_back(0, 0);
    nxt.emplace_back(n-1, m-1);

    vector<ii> nxt2;

    while (cnt > 0) {
        swap(nxt, nxt2);

        for (auto i : nxt2) {
            dfs(i.first, i.second);
        }

        nxt2.clear();
        ans++;
    }

    cout << ans << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4856 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 15 ms 6648 KB Output is correct
5 Correct 7 ms 2680 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 6 ms 2428 KB Output is correct
11 Correct 6 ms 2936 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 7 ms 2680 KB Output is correct
14 Correct 7 ms 2680 KB Output is correct
15 Correct 21 ms 4848 KB Output is correct
16 Correct 23 ms 4856 KB Output is correct
17 Correct 17 ms 4472 KB Output is correct
18 Correct 16 ms 6708 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 30840 KB Output is correct
2 Correct 69 ms 11252 KB Output is correct
3 Correct 410 ms 34180 KB Output is correct
4 Correct 118 ms 16888 KB Output is correct
5 Correct 257 ms 26368 KB Output is correct
6 Correct 1029 ms 174160 KB Output is correct
7 Correct 34 ms 32248 KB Output is correct
8 Correct 32 ms 30712 KB Output is correct
9 Correct 5 ms 1020 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 33 ms 31608 KB Output is correct
12 Correct 4 ms 1588 KB Output is correct
13 Correct 70 ms 11640 KB Output is correct
14 Correct 42 ms 8740 KB Output is correct
15 Correct 39 ms 9336 KB Output is correct
16 Correct 33 ms 4344 KB Output is correct
17 Correct 170 ms 17436 KB Output is correct
18 Correct 139 ms 17016 KB Output is correct
19 Correct 119 ms 16120 KB Output is correct
20 Correct 101 ms 15068 KB Output is correct
21 Correct 249 ms 26344 KB Output is correct
22 Correct 256 ms 25432 KB Output is correct
23 Correct 316 ms 21880 KB Output is correct
24 Correct 242 ms 27088 KB Output is correct
25 Correct 555 ms 34808 KB Output is correct
26 Runtime error 1081 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Correct 1452 ms 862180 KB Output is correct
28 Correct 1025 ms 174424 KB Output is correct
29 Correct 985 ms 148820 KB Output is correct
30 Correct 1174 ms 350496 KB Output is correct
31 Correct 741 ms 29716 KB Output is correct
32 Correct 1312 ms 626560 KB Output is correct