oj.uz

Submission #598697

# Submission time Handle Problem Language Result Execution time Memory
598697 2022-07-18T17:54:41 Z stevancv Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 1483 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;
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 34 ms 12756 KB Output is correct
2 Correct 1 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 6 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 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 4 ms 3924 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 11 ms 5716 KB Output is correct
13 Correct 5 ms 4416 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 28 ms 12244 KB Output is correct
16 Correct 33 ms 12684 KB Output is correct
17 Correct 21 ms 11716 KB Output is correct
18 Correct 11 ms 8184 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32652 KB Output is correct
2 Correct 99 ms 50240 KB Output is correct
3 Correct 457 ms 314180 KB Output is correct
4 Correct 141 ms 76332 KB Output is correct
5 Correct 709 ms 717480 KB Output is correct
6 Correct 1161 ms 305592 KB Output is correct
7 Correct 16 ms 34132 KB Output is correct
8 Correct 15 ms 32724 KB Output is correct
9 Correct 4 ms 1876 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 17 ms 33084 KB Output is correct
12 Correct 3 ms 3284 KB Output is correct
13 Correct 101 ms 50308 KB Output is correct
14 Correct 59 ms 30892 KB Output is correct
15 Correct 60 ms 34920 KB Output is correct
16 Correct 47 ms 22028 KB Output is correct
17 Correct 248 ms 119800 KB Output is correct
18 Correct 230 ms 119832 KB Output is correct
19 Correct 140 ms 76272 KB Output is correct
20 Correct 121 ms 83148 KB Output is correct
21 Correct 291 ms 204124 KB Output is correct
22 Correct 734 ms 717472 KB Output is correct
23 Correct 472 ms 217480 KB Output is correct
24 Correct 340 ms 284156 KB Output is correct
25 Correct 1006 ms 424512 KB Output is correct
26 Runtime error 566 ms 1048576 KB Execution killed with signal 9
27 Correct 914 ms 817412 KB Output is correct
28 Correct 1138 ms 305664 KB Output is correct
29 Correct 1033 ms 284616 KB Output is correct
30 Correct 963 ms 442676 KB Output is correct
31 Correct 1483 ms 362032 KB Output is correct
32 Correct 959 ms 816312 KB Output is correct