oj.uz

Submission #893145

# Submission time Handle Problem Language Result Execution time Memory
893145 2023-12-26T15:01:01 Z vanea Tracks in the Snow (BOI13_tracks) C++14
21.5625 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int label = 1, n, m;
const int mxN = 4e3+10;
const int mxN1 = 1e6+10;

vector<int> adj[mxN];
bool vis[mxN][mxN];
char matrix[mxN][mxN];
int idx[mxN][mxN], d[mxN1];

vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};

void dfs(int i, int j) {
    char c = matrix[i][j];
    idx[i][j] = label;
    vis[i][j] = true;
    for(int k = 0; k < 4; k++) {
        int a = i + xy[k], b = j + yx[k];
        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(matrix[a][b] == '.') continue;
        if(matrix[a][b] == c) {
            if(!vis[a][b]) dfs(a, b);
        }
        else {
            if(vis[a][b]) {
                adj[label].push_back(idx[a][b]);
                adj[idx[a][b]].push_back(label);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(matrix[i][j] != '.' && !vis[i][j]) {
                dfs(i, j);
                ++label;
            }
        }
    }
    queue<int> q;
    q.push(1);
    d[1] = 1;
    int ans = 0;
    while(!q.empty()) {
        auto node = q.front();
        q.pop();
        ans = max(ans, d[node]);
        for(auto it : adj[node]) {
            if(d[it] == 0) {
                d[it] = d[node]+1;
                q.push(it);
            }
        }
    }
    cout << ans;
}

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 34908 KB Execution killed with signal 11
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 9 ms 18268 KB Output is correct
5 Runtime error 16 ms 28344 KB Execution killed with signal 11
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 7004 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Runtime error 12 ms 19772 KB Execution killed with signal 11
11 Correct 4 ms 10076 KB Output is correct
12 Runtime error 17 ms 28944 KB Execution killed with signal 11
13 Runtime error 17 ms 28408 KB Execution killed with signal 11
14 Runtime error 16 ms 28508 KB Execution killed with signal 11
15 Runtime error 21 ms 34776 KB Execution killed with signal 11
16 Runtime error 21 ms 34848 KB Execution killed with signal 11
17 Runtime error 22 ms 34416 KB Execution killed with signal 11
18 Correct 9 ms 18268 KB Output is correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 194340 KB Execution killed with signal 11
2 Runtime error 46 ms 71068 KB Execution killed with signal 11
3 Runtime error 217 ms 212632 KB Execution killed with signal 11
4 Runtime error 79 ms 107600 KB Execution killed with signal 11
5 Runtime error 162 ms 163600 KB Execution killed with signal 11
6 Runtime error 394 ms 301560 KB Execution killed with signal 11
7 Runtime error 99 ms 196256 KB Execution killed with signal 11
8 Runtime error 99 ms 194256 KB Execution killed with signal 11
9 Runtime error 8 ms 10328 KB Execution killed with signal 11
10 Correct 1 ms 4956 KB Output is correct
11 Correct 16 ms 96400 KB Output is correct
12 Runtime error 9 ms 14680 KB Execution killed with signal 11
13 Runtime error 50 ms 71168 KB Execution killed with signal 11
14 Runtime error 45 ms 55120 KB Execution killed with signal 11
15 Runtime error 40 ms 59988 KB Execution killed with signal 11
16 Runtime error 23 ms 30044 KB Execution killed with signal 11
17 Runtime error 105 ms 113308 KB Execution killed with signal 11
18 Runtime error 84 ms 112808 KB Execution killed with signal 11
19 Runtime error 80 ms 107600 KB Execution killed with signal 11
20 Runtime error 98 ms 98072 KB Execution killed with signal 11
21 Runtime error 163 ms 168760 KB Execution killed with signal 11
22 Runtime error 147 ms 163408 KB Execution killed with signal 11
23 Runtime error 124 ms 137424 KB Execution killed with signal 11
24 Runtime error 152 ms 168736 KB Execution killed with signal 11
25 Runtime error 255 ms 212508 KB Execution killed with signal 11
26 Correct 1194 ms 1048576 KB Output is correct
27 Execution timed out 3422 ms 1048576 KB Time limit exceeded
28 Runtime error 409 ms 301484 KB Execution killed with signal 11
29 Runtime error 444 ms 378316 KB Execution killed with signal 11
30 Runtime error 403 ms 320856 KB Execution killed with signal 11
31 Runtime error 160 ms 175184 KB Execution killed with signal 11
32 Execution timed out 3548 ms 1048576 KB Time limit exceeded