oj.uz

Submission #598688

# Submission time Handle Problem Language Result Execution time Memory
598688 2022-07-18T17:45:21 Z stevancv Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 1458 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], c[N][N], n, m, iden;
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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13116 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 10 ms 7764 KB Output is correct
5 Correct 5 ms 4436 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 924 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 4 ms 3028 KB Output is correct
12 Correct 13 ms 5844 KB Output is correct
13 Correct 4 ms 4436 KB Output is correct
14 Correct 4 ms 4440 KB Output is correct
15 Correct 24 ms 12580 KB Output is correct
16 Correct 35 ms 13076 KB Output is correct
17 Correct 22 ms 12160 KB Output is correct
18 Correct 11 ms 7772 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 32408 KB Output is correct
2 Correct 98 ms 51748 KB Output is correct
3 Correct 466 ms 327516 KB Output is correct
4 Correct 148 ms 83176 KB Output is correct
5 Correct 736 ms 730740 KB Output is correct
6 Correct 1090 ms 304628 KB Output is correct
7 Correct 14 ms 33820 KB Output is correct
8 Correct 15 ms 32468 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 14 ms 32852 KB Output is correct
12 Correct 3 ms 3284 KB Output is correct
13 Correct 96 ms 51784 KB Output is correct
14 Correct 57 ms 31952 KB Output is correct
15 Correct 57 ms 36912 KB Output is correct
16 Correct 47 ms 22868 KB Output is correct
17 Correct 248 ms 123940 KB Output is correct
18 Correct 234 ms 127624 KB Output is correct
19 Correct 138 ms 83144 KB Output is correct
20 Correct 121 ms 86796 KB Output is correct
21 Correct 289 ms 212920 KB Output is correct
22 Correct 769 ms 730720 KB Output is correct
23 Correct 467 ms 225760 KB Output is correct
24 Correct 329 ms 293740 KB Output is correct
25 Correct 1036 ms 455748 KB Output is correct
26 Runtime error 581 ms 1048576 KB Execution killed with signal 9
27 Correct 758 ms 668604 KB Output is correct
28 Correct 1068 ms 304476 KB Output is correct
29 Correct 987 ms 280308 KB Output is correct
30 Correct 891 ms 394272 KB Output is correct
31 Correct 1458 ms 386936 KB Output is correct
32 Correct 856 ms 672096 KB Output is correct