oj.uz

Submission #757696

# Submission time Handle Problem Language Result Execution time Memory
757696 2023-06-13T15:00:39 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;
    vector<int> stk;
    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 ++) {
        int k = edge.size();
        auto cur = std::move(edge);
        for (int k : cur)
            dfs(k, d);
    }
    cout << res << '\n';
    
    

    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:55:13: warning: unused variable 'k' [-Wunused-variable]
   55 |         int k = edge.size();
      |             ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 19336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 33 ms 12864 KB Output is correct
5 Correct 7 ms 3784 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 6 ms 3540 KB Output is correct
11 Correct 9 ms 3560 KB Output is correct
12 Correct 17 ms 7124 KB Output is correct
13 Correct 6 ms 3796 KB Output is correct
14 Correct 6 ms 3788 KB Output is correct
15 Correct 37 ms 16820 KB Output is correct
16 Correct 47 ms 19264 KB Output is correct
17 Correct 36 ms 12532 KB Output is correct
18 Correct 31 ms 12852 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 158 ms 79428 KB Output is correct
3 Correct 907 ms 672304 KB Output is correct
4 Correct 254 ms 142412 KB Output is correct
5 Correct 784 ms 433040 KB Output is correct
6 Runtime error 1621 ms 1048576 KB Execution killed with signal 9
7 Correct 3 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 2 ms 1364 KB Output is correct
13 Correct 152 ms 79232 KB Output is correct
14 Correct 89 ms 46068 KB Output is correct
15 Correct 96 ms 41568 KB Output is correct
16 Correct 76 ms 36772 KB Output is correct
17 Correct 379 ms 202804 KB Output is correct
18 Correct 344 ms 164484 KB Output is correct
19 Correct 251 ms 142228 KB Output is correct
20 Correct 209 ms 147768 KB Output is correct
21 Correct 532 ms 393492 KB Output is correct
22 Correct 791 ms 432912 KB Output is correct
23 Correct 767 ms 392412 KB Output is correct
24 Correct 591 ms 388916 KB Output is correct
25 Correct 1919 ms 661892 KB Output is correct
26 Execution timed out 2071 ms 1007300 KB Time limit exceeded
27 Runtime error 1639 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1642 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1828 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1655 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2084 ms 812340 KB Time limit exceeded
32 Runtime error 1638 ms 1048576 KB Execution killed with signal 9