oj.uz

Submission #757693

# Submission time Handle Problem Language Result Execution time Memory
757693 2023-06-13T14:57:44 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<string> mat(n);
    for (string& s : mat) {
        cin >> s;
    }
    auto id = [m](int i, int j) { return i* m + j;};
    vector<vector<pair<int,int>>> adj(n * m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (auto [di, dj] : {pair{0, -1}, {0, 1}, {-1, 0}, {1, 0}}) {
                int ni = i + di;
                int nj = j + dj;
                if (clamp(ni, 0,n-1) == ni && clamp(nj, 0, m-1) == nj) {
                    if (mat[ni][nj] == '.' || mat[i][j] == '.') continue;
                    int c = mat[i][j] != mat[ni][nj];
                    adj[id(i, j)].push_back({id(ni, nj), c});
                }
            }
        }
    }

    static constexpr int inf = 1e9;
    vector<int> dist(n*m, inf), vis(n*m, 0);
    int res = 0;
    vector<int> edge;
    auto dfs = [&](int i, int d) -> void {
        vector<int> stk{i};
        while (stk.size()) {
            int i = stk.back();
            stk.pop_back();
            vis[i] = 1;
            dist[i] = d;
            for (auto [e, ec]: adj[i]) {
                if (vis[e]) continue;
                if (ec) {vis[e] = 1, edge.push_back(e);}
                else
                    stk.push_back(e);
            }
            res = max(res, dist[i]);
        }
    };
    dfs(0, 1);
    for (int d = 2; edge.size(); d ++) {
        auto cur = std::move(edge);
        for (int k : cur)
            dfs(k, d);
    }
    cout << res << '\n';
    
    

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 19384 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 34 ms 12736 KB Output is correct
5 Correct 8 ms 3872 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 448 KB Output is correct
8 Correct 2 ms 708 KB Output is correct
9 Correct 1 ms 712 KB Output is correct
10 Correct 6 ms 3540 KB Output is correct
11 Correct 8 ms 3524 KB Output is correct
12 Correct 17 ms 7064 KB Output is correct
13 Correct 6 ms 3796 KB Output is correct
14 Correct 7 ms 3788 KB Output is correct
15 Correct 40 ms 16876 KB Output is correct
16 Correct 56 ms 19404 KB Output is correct
17 Correct 40 ms 12624 KB Output is correct
18 Correct 37 ms 12744 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2512 KB Output is correct
2 Correct 165 ms 79536 KB Output is correct
3 Correct 979 ms 672576 KB Output is correct
4 Correct 260 ms 142588 KB Output is correct
5 Correct 848 ms 433212 KB Output is correct
6 Runtime error 1802 ms 1048576 KB Execution killed with signal 9
7 Correct 4 ms 2132 KB Output is correct
8 Correct 4 ms 2388 KB Output is correct
9 Correct 6 ms 3412 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 3 ms 2132 KB Output is correct
12 Correct 3 ms 1364 KB Output is correct
13 Correct 165 ms 79172 KB Output is correct
14 Correct 107 ms 46080 KB Output is correct
15 Correct 105 ms 41568 KB Output is correct
16 Correct 81 ms 36788 KB Output is correct
17 Correct 416 ms 202880 KB Output is correct
18 Correct 365 ms 164464 KB Output is correct
19 Correct 285 ms 142116 KB Output is correct
20 Correct 250 ms 147724 KB Output is correct
21 Correct 555 ms 393548 KB Output is correct
22 Correct 855 ms 432788 KB Output is correct
23 Correct 845 ms 392504 KB Output is correct
24 Correct 611 ms 388836 KB Output is correct
25 Correct 1921 ms 661924 KB Output is correct
26 Execution timed out 2088 ms 1008184 KB Time limit exceeded
27 Runtime error 1677 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1753 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1719 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1767 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2106 ms 812392 KB Time limit exceeded
32 Runtime error 1683 ms 1048576 KB Execution killed with signal 9