oj.uz

Submission #757705

# Submission time Handle Problem Language Result Execution time Memory
757705 2023-06-13T15:22:01 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
3.33333 / 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), vis2(n*m, 0);
    int res = 0;
    vector<int> edge, cur;
    vector<int> stk;
    stk.reserve(1e9);
    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)
                    stk.push_back(e);
            }
            res = max(res, dist[i]);
        }
    };
    auto dfs_min = [&](int i) -> int {
        stk.clear();
        stk.push_back(i);
        int res = inf;
        while (stk.size()) {
            int i = stk.back();
            stk.pop_back();
            vis2[i] = 1;
            for (auto [e, ec]: adj[i]) {
                if (ec) res = min(res, dist[e]);
                if (vis2[e]) continue;
                if (!ec)
                    stk.push_back(e);
            }
        }
        return res;
    };
    dfs(0, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[id(i, j)]) continue;
            if (mat[i][j] == '.') continue;
            int d = dfs_min(id(i, j))+1;
            dfs(id(i, j), d);
        }
    }
    cout << res << '\n';
    
    

    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 20052 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Incorrect 37 ms 13092 KB Output isn't correct
5 Incorrect 9 ms 4052 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 Correct 2 ms 724 KB Output is correct
9 Incorrect 1 ms 724 KB Output isn't correct
10 Incorrect 8 ms 3920 KB Output isn't correct
11 Correct 11 ms 3672 KB Output is correct
12 Incorrect 21 ms 7316 KB Output isn't correct
13 Incorrect 10 ms 4052 KB Output isn't correct
14 Incorrect 8 ms 4052 KB Output isn't correct
15 Incorrect 41 ms 17748 KB Output isn't correct
16 Incorrect 58 ms 20044 KB Output isn't correct
17 Incorrect 32 ms 13368 KB Output isn't correct
18 Incorrect 35 ms 13080 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2644 KB Output isn't correct
2 Incorrect 156 ms 85344 KB Output isn't correct
3 Incorrect 967 ms 734752 KB Output isn't correct
4 Incorrect 245 ms 156876 KB Output isn't correct
5 Incorrect 756 ms 467952 KB Output isn't correct
6 Runtime error 1669 ms 1048576 KB Execution killed with signal 9
7 Incorrect 4 ms 2388 KB Output isn't correct
8 Incorrect 4 ms 2644 KB Output isn't correct
9 Incorrect 6 ms 3668 KB Output isn't correct
10 Incorrect 2 ms 1748 KB Output isn't correct
11 Incorrect 3 ms 2260 KB Output isn't correct
12 Incorrect 2 ms 1492 KB Output isn't correct
13 Incorrect 151 ms 85360 KB Output isn't correct
14 Incorrect 88 ms 49484 KB Output isn't correct
15 Incorrect 83 ms 45448 KB Output isn't correct
16 Incorrect 83 ms 39356 KB Output isn't correct
17 Incorrect 419 ms 218764 KB Output isn't correct
18 Incorrect 307 ms 180044 KB Output isn't correct
19 Incorrect 248 ms 156864 KB Output isn't correct
20 Incorrect 239 ms 161252 KB Output isn't correct
21 Incorrect 577 ms 429856 KB Output isn't correct
22 Incorrect 720 ms 468036 KB Output isn't correct
23 Incorrect 720 ms 422724 KB Output isn't correct
24 Incorrect 579 ms 424492 KB Output isn't correct
25 Incorrect 1253 ms 724612 KB Output isn't correct
26 Execution timed out 2082 ms 1042148 KB Time limit exceeded
27 Runtime error 1630 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1644 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1634 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1643 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2116 ms 851680 KB Time limit exceeded
32 Runtime error 1598 ms 1048576 KB Execution killed with signal 9