oj.uz

Submission #757698

# Submission time Handle Problem Language Result Execution time Memory
757698 2023-06-13T15:02:12 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
67.1875 / 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;
    vector<int> stk;
    stk.reserve(1e7);
    auto dfs = [&](int i, int d) -> void {
        stk.clear();
        stk.push_back(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 ++) {
        vector<int> cur;
        cur.reserve(1e7);
        swap(cur, 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 51 ms 19400 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 1 ms 524 KB Output is correct
4 Correct 33 ms 12868 KB Output is correct
5 Correct 7 ms 4084 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 1 ms 524 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 824 KB Output is correct
10 Correct 7 ms 3876 KB Output is correct
11 Correct 8 ms 3648 KB Output is correct
12 Correct 18 ms 7196 KB Output is correct
13 Correct 8 ms 4084 KB Output is correct
14 Correct 8 ms 4092 KB Output is correct
15 Correct 52 ms 17116 KB Output is correct
16 Correct 52 ms 19388 KB Output is correct
17 Correct 31 ms 12848 KB Output is correct
18 Correct 34 ms 12876 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10648 KB Output is correct
2 Correct 158 ms 80936 KB Output is correct
3 Execution timed out 2100 ms 690756 KB Time limit exceeded
4 Correct 259 ms 143480 KB Output is correct
5 Execution timed out 2025 ms 452764 KB Time limit exceeded
6 Runtime error 1549 ms 1048576 KB Execution killed with signal 9
7 Correct 27 ms 10108 KB Output is correct
8 Correct 32 ms 10928 KB Output is correct
9 Correct 7 ms 4000 KB Output is correct
10 Correct 17 ms 6776 KB Output is correct
11 Correct 20 ms 6412 KB Output is correct
12 Correct 63 ms 12424 KB Output is correct
13 Correct 153 ms 80728 KB Output is correct
14 Correct 92 ms 47372 KB Output is correct
15 Correct 929 ms 55616 KB Output is correct
16 Correct 80 ms 38476 KB Output is correct
17 Correct 435 ms 208992 KB Output is correct
18 Execution timed out 2024 ms 179380 KB Time limit exceeded
19 Correct 266 ms 143156 KB Output is correct
20 Correct 901 ms 164020 KB Output is correct
21 Execution timed out 2118 ms 410312 KB Time limit exceeded
22 Execution timed out 2105 ms 468912 KB Time limit exceeded
23 Correct 780 ms 400072 KB Output is correct
24 Execution timed out 2109 ms 407080 KB Time limit exceeded
25 Execution timed out 2076 ms 677508 KB Time limit exceeded
26 Execution timed out 2117 ms 1002284 KB Time limit exceeded
27 Runtime error 1474 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1488 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1476 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1501 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2120 ms 812316 KB Time limit exceeded
32 Runtime error 1707 ms 1048576 KB Execution killed with signal 9