oj.uz

Submission #598682

# Submission time Handle Problem Language Result Execution time Memory
598682 2022-07-18T17:34:01 Z stevancv Tracks in the Snow (BOI13_tracks) C++14
5.52083 / 100
 1203 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]);
            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]);
        }
    }
    assert(c[0][0] == c[n - 1][m - 1]);
    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
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 11820 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Incorrect 9 ms 7796 KB Output isn't correct
5 Incorrect 4 ms 4052 KB Output isn't correct
6 Incorrect 0 ms 468 KB Output isn't correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Correct 1 ms 852 KB Output is correct
9 Incorrect 1 ms 1236 KB Output isn't correct
10 Incorrect 3 ms 3668 KB Output isn't correct
11 Correct 3 ms 3112 KB Output is correct
12 Incorrect 9 ms 5332 KB Output isn't correct
13 Incorrect 4 ms 4052 KB Output isn't correct
14 Incorrect 4 ms 4052 KB Output isn't correct
15 Incorrect 21 ms 11292 KB Output isn't correct
16 Incorrect 26 ms 11904 KB Output isn't correct
17 Incorrect 16 ms 10300 KB Output isn't correct
18 Incorrect 9 ms 7828 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 32280 KB Output isn't correct
2 Incorrect 71 ms 43720 KB Output isn't correct
3 Incorrect 347 ms 264236 KB Output isn't correct
4 Incorrect 106 ms 70744 KB Output isn't correct
5 Incorrect 445 ms 519832 KB Output isn't correct
6 Incorrect 934 ms 302796 KB Output isn't correct
7 Incorrect 14 ms 33620 KB Output isn't correct
8 Incorrect 15 ms 32188 KB Output isn't correct
9 Incorrect 3 ms 1620 KB Output isn't correct
10 Incorrect 1 ms 724 KB Output isn't correct
11 Incorrect 13 ms 32692 KB Output isn't correct
12 Incorrect 2 ms 2772 KB Output isn't correct
13 Incorrect 67 ms 43632 KB Output isn't correct
14 Incorrect 41 ms 27164 KB Output isn't correct
15 Incorrect 40 ms 30240 KB Output isn't correct
16 Incorrect 35 ms 19276 KB Output isn't correct
17 Incorrect 169 ms 102584 KB Output isn't correct
18 Incorrect 127 ms 101740 KB Output isn't correct
19 Incorrect 107 ms 70736 KB Output isn't correct
20 Incorrect 93 ms 72440 KB Output isn't correct
21 Incorrect 215 ms 175116 KB Output isn't correct
22 Incorrect 428 ms 519644 KB Output isn't correct
23 Incorrect 308 ms 184880 KB Output isn't correct
24 Incorrect 233 ms 223480 KB Output isn't correct
25 Incorrect 495 ms 348824 KB Output isn't correct
26 Runtime error 607 ms 1048576 KB Execution killed with signal 9
27 Correct 801 ms 668464 KB Output is correct
28 Incorrect 952 ms 302784 KB Output isn't correct
29 Incorrect 921 ms 280072 KB Output isn't correct
30 Incorrect 833 ms 394100 KB Output isn't correct
31 Incorrect 1203 ms 339092 KB Output isn't correct
32 Incorrect 830 ms 667632 KB Output isn't correct