oj.uz

Submission #134095

# Submission time Handle Problem Language Result Execution time Memory
134095 2019-07-22T04:21:02 Z fredbr Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1434 ms 986852 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<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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4344 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 14 ms 5368 KB Output is correct
5 Correct 7 ms 2680 KB Output is correct
6 Correct 2 ms 504 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 1192 KB Output is correct
10 Correct 6 ms 2296 KB Output is correct
11 Correct 6 ms 2680 KB Output is correct
12 Correct 9 ms 2684 KB Output is correct
13 Correct 7 ms 2808 KB Output is correct
14 Correct 7 ms 2680 KB Output is correct
15 Correct 18 ms 4344 KB Output is correct
16 Correct 19 ms 4416 KB Output is correct
17 Correct 17 ms 4280 KB Output is correct
18 Correct 14 ms 5496 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 30584 KB Output is correct
2 Correct 66 ms 10360 KB Output is correct
3 Correct 403 ms 32420 KB Output is correct
4 Correct 117 ms 15480 KB Output is correct
5 Correct 284 ms 24312 KB Output is correct
6 Correct 922 ms 113092 KB Output is correct
7 Correct 34 ms 32120 KB Output is correct
8 Correct 34 ms 30584 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 33 ms 31480 KB Output is correct
12 Correct 4 ms 1528 KB Output is correct
13 Correct 68 ms 10332 KB Output is correct
14 Correct 39 ms 7672 KB Output is correct
15 Correct 40 ms 8312 KB Output is correct
16 Correct 31 ms 3704 KB Output is correct
17 Correct 161 ms 16504 KB Output is correct
18 Correct 148 ms 16372 KB Output is correct
19 Correct 120 ms 15480 KB Output is correct
20 Correct 102 ms 14476 KB Output is correct
21 Correct 243 ms 25340 KB Output is correct
22 Correct 319 ms 24400 KB Output is correct
23 Correct 307 ms 20476 KB Output is correct
24 Correct 247 ms 25336 KB Output is correct
25 Correct 572 ms 32468 KB Output is correct
26 Correct 1434 ms 986852 KB Output is correct
27 Correct 1287 ms 621560 KB Output is correct
28 Correct 921 ms 113148 KB Output is correct
29 Correct 899 ms 87884 KB Output is correct
30 Correct 1012 ms 244728 KB Output is correct
31 Correct 601 ms 26372 KB Output is correct
32 Correct 1105 ms 454112 KB Output is correct