oj.uz

Submission #598693

# Submission time Handle Problem Language Result Execution time Memory
598693 2022-07-18T17:52:21 Z stevancv Tracks in the Snow (BOI13_tracks) C++14
40.8333 / 100
 1360 ms 1048576 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 4e3 + 2;
int a[N][N], n, m, iden;
short c[N][N];
bool Can(int x, int y) {return 0 <= x && x < n && 0 <= y && y < m && c[x][y] == -1;}
void Dfs(int i, int j) {
    c[i][j] = iden;
    if (Can(i - 1, j) && a[i - 1][j] == a[i][j]) Dfs(i - 1, j);
    if (Can(i, j - 1) && a[i][j - 1] == a[i][j]) Dfs(i, j - 1);
    if (Can(i + 1, j) && a[i + 1][j] == a[i][j]) Dfs(i + 1, j);
    if (Can(i, j + 1) && a[i][j + 1] == a[i][j]) Dfs(i, j + 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            c[i][j] = -1;
            if (s[j] == 'F') a[i][j] = 1;
            if (s[j] == 'R') a[i][j] = 2;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == -1 && a[i][j] > 0) {
                Dfs(i, j);
                iden += 1;
            }
        }
    }
    vector<set<int>> g(iden);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == -1) continue;
            if (i < n - 1 && c[i + 1][j] != c[i][j] && c[i + 1][j] != -1) {
                g[c[i][j]].insert(c[i + 1][j]);
                g[c[i + 1][j]].insert(c[i][j]);
            }
            if (j < m - 1 && c[i][j + 1] != c[i][j] && c[i][j + 1] != -1) {
                g[c[i][j]].insert(c[i][j + 1]);
                g[c[i][j + 1]].insert(c[i][j]);
            }
        }
    }
    vector<int> dist(iden, 1e9);
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (int u : g[s]) {
            if (dist[u] > dist[s] + 1) {
                dist[u] = dist[s] + 1;
                q.push(u);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < iden; i++) {
        smax(ans, dist[i] + 1);
    }
    cout << ans << en;
    return 0;
}

Subtask #1
23.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 25068 KB Execution killed with signal 11
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 11 ms 8096 KB Output is correct
5 Correct 5 ms 4308 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 5 ms 3924 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 12 ms 5656 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Runtime error 37 ms 23404 KB Execution killed with signal 11
16 Runtime error 47 ms 25060 KB Execution killed with signal 11
17 Runtime error 41 ms 22876 KB Execution killed with signal 11
18 Correct 12 ms 8112 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 32480 KB Output is correct
2 Runtime error 99 ms 60312 KB Execution killed with signal 11
3 Runtime error 535 ms 1048576 KB Execution killed with signal 9
4 Runtime error 462 ms 1048576 KB Execution killed with signal 9
5 Runtime error 452 ms 548556 KB Execution killed with signal 11
6 Runtime error 782 ms 1048576 KB Execution killed with signal 9
7 Correct 15 ms 33744 KB Output is correct
8 Correct 18 ms 32468 KB Output is correct
9 Correct 4 ms 1896 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 13 ms 32756 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct
13 Runtime error 88 ms 60324 KB Execution killed with signal 11
14 Runtime error 53 ms 41508 KB Execution killed with signal 11
15 Runtime error 55 ms 48588 KB Execution killed with signal 11
16 Runtime error 862 ms 1048576 KB Execution killed with signal 9
17 Runtime error 466 ms 1048576 KB Execution killed with signal 9
18 Runtime error 577 ms 1048576 KB Execution killed with signal 9
19 Runtime error 473 ms 1048576 KB Execution killed with signal 9
20 Runtime error 499 ms 1048576 KB Execution killed with signal 9
21 Runtime error 518 ms 1048576 KB Execution killed with signal 9
22 Runtime error 407 ms 548316 KB Execution killed with signal 11
23 Runtime error 526 ms 1048576 KB Execution killed with signal 9
24 Runtime error 523 ms 1048576 KB Execution killed with signal 9
25 Runtime error 521 ms 1048576 KB Execution killed with signal 9
26 Runtime error 583 ms 1048576 KB Execution killed with signal 9
27 Correct 1360 ms 817384 KB Output is correct
28 Runtime error 750 ms 1048576 KB Execution killed with signal 9
29 Runtime error 742 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1296 ms 1048576 KB Execution killed with signal 9
31 Runtime error 553 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1218 ms 1048576 KB Execution killed with signal 9