oj.uz

Submission #134094

# Submission time Handle Problem Language Result Execution time Memory
134094 2019-07-22T04:20:14 Z fredbr Tracks in the Snow (BOI13_tracks) C++17
34.1667 / 100
 1098 ms 621560 KB 
#include <bits/stdc++.h>

using namespace std;

int const maxn = 4010;

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

using ii = pair<short, short>;

vector<ii> nxt, nxt2;

static int const dx[] = {0, 1, 0, -1};
static int const dy[] = {1, 0, -1, 0};

void dfs(short x, short y) {

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

    vis[x][y] = 2;
    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] != 0) continue;

            if (v[xx][yy] == v[x][y]) dfs(xx, yy);
            else if (v[xx][yy] != '.' and vis[xx][yy] == 0) {
                vis[xx][yy] = 1;
                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);

    nxt.reserve(n*m);
    nxt2.reserve(n*m);
    
    while (cnt > 0) {
        swap(nxt, nxt2);

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

        nxt2.clear();
        ans++;
    }

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

Subtask #1
16.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2300 KB Output isn't correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Incorrect 10 ms 4984 KB Output isn't correct
5 Correct 7 ms 2680 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 4 ms 1144 KB Output is correct
10 Correct 6 ms 2424 KB Output is correct
11 Incorrect 3 ms 1144 KB Output isn't correct
12 Incorrect 6 ms 2680 KB Output isn't correct
13 Correct 7 ms 2680 KB Output is correct
14 Correct 7 ms 2680 KB Output is correct
15 Incorrect 8 ms 2296 KB Output isn't correct
16 Incorrect 7 ms 2300 KB Output isn't correct
17 Incorrect 8 ms 2296 KB Output isn't correct
18 Incorrect 11 ms 5112 KB Output isn't correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 30584 KB Output is correct
2 Incorrect 30 ms 5284 KB Output isn't correct
3 Incorrect 268 ms 32376 KB Output isn't correct
4 Incorrect 72 ms 7800 KB Output isn't correct
5 Incorrect 148 ms 12168 KB Output isn't correct
6 Incorrect 430 ms 78568 KB Output isn't correct
7 Correct 34 ms 32120 KB Output is correct
8 Correct 32 ms 30584 KB Output is correct
9 Correct 8 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 33 ms 31472 KB Output is correct
12 Correct 4 ms 1528 KB Output is correct
13 Incorrect 28 ms 5236 KB Output isn't correct
14 Incorrect 21 ms 3960 KB Output isn't correct
15 Incorrect 31 ms 8312 KB Output isn't correct
16 Incorrect 16 ms 3704 KB Output isn't correct
17 Incorrect 79 ms 16504 KB Output isn't correct
18 Incorrect 81 ms 8184 KB Output isn't correct
19 Incorrect 82 ms 7772 KB Output isn't correct
20 Incorrect 59 ms 7292 KB Output isn't correct
21 Incorrect 146 ms 12536 KB Output isn't correct
22 Incorrect 143 ms 12096 KB Output isn't correct
23 Incorrect 123 ms 10208 KB Output isn't correct
24 Incorrect 144 ms 12552 KB Output isn't correct
25 Incorrect 310 ms 16148 KB Output isn't correct
26 Incorrect 193 ms 14220 KB Output isn't correct
27 Incorrect 1098 ms 621560 KB Output isn't correct
28 Incorrect 415 ms 78580 KB Output isn't correct
29 Incorrect 439 ms 83960 KB Output isn't correct
30 Correct 997 ms 244744 KB Output is correct
31 Incorrect 164 ms 12960 KB Output isn't correct
32 Incorrect 273 ms 32504 KB Output isn't correct