oj.uz

Submission #893148

# Submission time Handle Problem Language Result Execution time Memory
893148 2023-12-26T15:02:35 Z vanea Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 896 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 = 5e6+10;

vector<int> adj[mxN1];
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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 138492 KB Output is correct
2 Correct 26 ms 122972 KB Output is correct
3 Correct 26 ms 123080 KB Output is correct
4 Correct 40 ms 136796 KB Output is correct
5 Correct 30 ms 128488 KB Output is correct
6 Correct 26 ms 122972 KB Output is correct
7 Correct 27 ms 122972 KB Output is correct
8 Correct 29 ms 123228 KB Output is correct
9 Correct 30 ms 125272 KB Output is correct
10 Correct 30 ms 128348 KB Output is correct
11 Correct 29 ms 126220 KB Output is correct
12 Correct 35 ms 129364 KB Output is correct
13 Correct 30 ms 128348 KB Output is correct
14 Correct 30 ms 128344 KB Output is correct
15 Correct 45 ms 137812 KB Output is correct
16 Correct 48 ms 138380 KB Output is correct
17 Correct 45 ms 136788 KB Output is correct
18 Correct 43 ms 136528 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 211568 KB Output is correct
2 Correct 104 ms 163088 KB Output is correct
3 Correct 456 ms 280948 KB Output is correct
4 Correct 126 ms 176720 KB Output is correct
5 Correct 476 ms 355380 KB Output is correct
6 Correct 830 ms 314148 KB Output is correct
7 Correct 43 ms 213596 KB Output is correct
8 Correct 40 ms 211536 KB Output is correct
9 Correct 29 ms 123484 KB Output is correct
10 Correct 27 ms 123164 KB Output is correct
11 Correct 40 ms 213548 KB Output is correct
12 Correct 28 ms 125788 KB Output is correct
13 Correct 100 ms 161852 KB Output is correct
14 Correct 70 ms 148308 KB Output is correct
15 Correct 63 ms 152412 KB Output is correct
16 Correct 63 ms 135452 KB Output is correct
17 Correct 213 ms 192080 KB Output is correct
18 Correct 159 ms 187392 KB Output is correct
19 Correct 125 ms 174612 KB Output is correct
20 Correct 128 ms 176352 KB Output is correct
21 Correct 282 ms 232264 KB Output is correct
22 Correct 523 ms 350716 KB Output is correct
23 Correct 406 ms 227600 KB Output is correct
24 Correct 277 ms 249624 KB Output is correct
25 Correct 787 ms 294228 KB Output is correct
26 Runtime error 787 ms 1048576 KB Execution killed with signal 9
27 Correct 892 ms 761988 KB Output is correct
28 Correct 756 ms 314932 KB Output is correct
29 Correct 734 ms 342852 KB Output is correct
30 Correct 749 ms 439964 KB Output is correct
31 Correct 896 ms 330788 KB Output is correct
32 Correct 862 ms 719172 KB Output is correct