oj.uz

Submission #1109313

# Submission time Handle Problem Language Result Execution time Memory
1109313 2024-11-06T12:10:59 Z Kirill22 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1129 ms 297824 KB 
#include "bits/stdc++.h"
 
using namespace std;
 
vector<pair<int, int>> d{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    auto check = [&] (int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    };
    char c = a[0][0];
    vector<pair<int, int>> ts;
    vector<vector<int>> usd(n, vector<int> (m));
    auto dfs = [&] (int x, int y) {
        vector<pair<int, int>> qu = {{x, y}};
        usd[x][y] = 1;
        for (int i = 0; i < (int) qu.size(); i++) {
            auto [x, y] = qu[i];
            ts.push_back({x, y});
            for (auto [x2, y2] : d) {
                x2 += x, y2 += y;
                if (check(x2, y2) && a[x2][y2] == c && !usd[x2][y2]) {
                    usd[x2][y2] = 1;
                    qu.push_back({x2, y2});
                }
            }
        }
    };
    dfs(0, 0);
    int ans = 0;
    while (1) {
        c = c == 'F' ? 'R' : 'F';
        ans++;
        auto ct = ts;
        ts.clear();
        for (auto [x, y] : ct) {
            for (auto [x2, y2] : d) {
                x2 += x, y2 += y;
                if (check(x2, y2) && a[x2][y2] == c && !usd[x2][y2]) {
                    dfs(x2, y2);
                }
            }
        }
        if (ts.empty()) {
            break;
        }
    }
    cout << ans << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2128 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 11 ms 3108 KB Output is correct
5 Correct 3 ms 848 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 4 ms 848 KB Output is correct
11 Correct 4 ms 1228 KB Output is correct
12 Correct 8 ms 1104 KB Output is correct
13 Correct 3 ms 848 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 15 ms 2088 KB Output is correct
16 Correct 21 ms 2140 KB Output is correct
17 Correct 10 ms 1872 KB Output is correct
18 Correct 14 ms 3196 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 59 ms 9732 KB Output is correct
3 Correct 333 ms 96964 KB Output is correct
4 Correct 77 ms 22856 KB Output is correct
5 Correct 268 ms 54556 KB Output is correct
6 Correct 1129 ms 224252 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 4 ms 1020 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 1060 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 57 ms 9936 KB Output is correct
14 Correct 39 ms 5896 KB Output is correct
15 Correct 26 ms 6504 KB Output is correct
16 Correct 39 ms 4432 KB Output is correct
17 Correct 172 ms 24704 KB Output is correct
18 Correct 94 ms 24404 KB Output is correct
19 Correct 84 ms 22856 KB Output is correct
20 Correct 76 ms 21072 KB Output is correct
21 Correct 188 ms 56348 KB Output is correct
22 Correct 265 ms 54344 KB Output is correct
23 Correct 305 ms 47132 KB Output is correct
24 Correct 205 ms 54856 KB Output is correct
25 Correct 444 ms 96840 KB Output is correct
26 Correct 830 ms 275212 KB Output is correct
27 Correct 1067 ms 297824 KB Output is correct
28 Correct 1089 ms 224788 KB Output is correct
29 Correct 1053 ms 218732 KB Output is correct
30 Correct 1056 ms 266248 KB Output is correct
31 Correct 883 ms 63740 KB Output is correct
32 Correct 910 ms 296360 KB Output is correct