oj.uz

Submission #366953

# Submission time Handle Problem Language Result Execution time Memory
366953 2021-02-15T19:59:10 Z vishesh312 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1148 ms 984844 KB 
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

using ll = long long;
const int mod = 1e9+7;
vector<string> v;
int n, m;
int ans = 0;
array<vector<array<int, 2>>, 2> cur;

bool isValid(int i, int j) {
    return i < n and i >= 0 and j < m and j >= 0 and v[i][j] != '.';
}

vector<array<int, 2>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void dfs(array<int, 2> a) {
    char c = v[a[0]][a[1]];
    v[a[0]][a[1]] = '.';
    for (auto m : moves) {
        int nx = a[0] + m[0], ny = a[1] + m[1];
        if (isValid(nx, ny)) {
            if (v[nx][ny] == c) {
                dfs({nx, ny});
            } else {
                cur[ans&1?0:1].push_back({nx, ny});
            }
        }
    }
}

void solve(int tc) {
    cin >> n >> m;
    v.resize(n);
    for (auto &x : v) cin >> x;
    cur[0].push_back({0, 0});
    while (!cur[ans&1].empty()) {
        for (auto x : cur[ans&1]) {
            if (isValid(x[0], x[1])) {
                dfs(x);
            }
        }
        cur[ans&1].clear();
        ++ans;
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1260 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 9 ms 2172 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 1004 KB Output is correct
12 Correct 6 ms 748 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 14 ms 1132 KB Output is correct
16 Correct 18 ms 1260 KB Output is correct
17 Correct 8 ms 1004 KB Output is correct
18 Correct 10 ms 2152 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 43 ms 3820 KB Output is correct
3 Correct 223 ms 33516 KB Output is correct
4 Correct 52 ms 8300 KB Output is correct
5 Correct 209 ms 19436 KB Output is correct
6 Correct 786 ms 102660 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 788 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 44 ms 3820 KB Output is correct
14 Correct 25 ms 2412 KB Output is correct
15 Correct 16 ms 2668 KB Output is correct
16 Correct 25 ms 1900 KB Output is correct
17 Correct 110 ms 9192 KB Output is correct
18 Correct 62 ms 8812 KB Output is correct
19 Correct 44 ms 8300 KB Output is correct
20 Correct 53 ms 7660 KB Output is correct
21 Correct 134 ms 20076 KB Output is correct
22 Correct 206 ms 19436 KB Output is correct
23 Correct 222 ms 17132 KB Output is correct
24 Correct 156 ms 19564 KB Output is correct
25 Correct 322 ms 33388 KB Output is correct
26 Correct 1148 ms 984844 KB Output is correct
27 Correct 737 ms 257380 KB Output is correct
28 Correct 789 ms 103484 KB Output is correct
29 Correct 778 ms 95952 KB Output is correct
30 Correct 754 ms 179892 KB Output is correct
31 Correct 740 ms 24036 KB Output is correct
32 Correct 710 ms 284148 KB Output is correct