oj.uz

Submission #598695

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

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12664 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 11 ms 8148 KB Output is correct
5 Correct 4 ms 4308 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 4 ms 3896 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 12 ms 5716 KB Output is correct
13 Correct 7 ms 4308 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 27 ms 12232 KB Output is correct
16 Correct 35 ms 12672 KB Output is correct
17 Correct 20 ms 11604 KB Output is correct
18 Correct 10 ms 8148 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32468 KB Output is correct
2 Correct 99 ms 50176 KB Output is correct
3 Correct 465 ms 314184 KB Output is correct
4 Correct 138 ms 76300 KB Output is correct
5 Correct 734 ms 717740 KB Output is correct
6 Correct 1115 ms 305704 KB Output is correct
7 Correct 16 ms 33752 KB Output is correct
8 Correct 16 ms 32440 KB Output is correct
9 Correct 4 ms 1876 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 18 ms 32804 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct
13 Correct 110 ms 50420 KB Output is correct
14 Correct 58 ms 30900 KB Output is correct
15 Correct 61 ms 34912 KB Output is correct
16 Correct 48 ms 22024 KB Output is correct
17 Correct 264 ms 119840 KB Output is correct
18 Correct 254 ms 119704 KB Output is correct
19 Correct 159 ms 76460 KB Output is correct
20 Correct 130 ms 83148 KB Output is correct
21 Correct 305 ms 204336 KB Output is correct
22 Correct 725 ms 717552 KB Output is correct
23 Correct 485 ms 217548 KB Output is correct
24 Correct 364 ms 284028 KB Output is correct
25 Correct 1074 ms 424552 KB Output is correct
26 Runtime error 692 ms 1048576 KB Execution killed with signal 9
27 Correct 1079 ms 817384 KB Output is correct
28 Correct 1233 ms 305656 KB Output is correct
29 Correct 1099 ms 284480 KB Output is correct
30 Correct 1093 ms 442696 KB Output is correct
31 Correct 1639 ms 361984 KB Output is correct
32 Correct 1052 ms 816300 KB Output is correct