oj.uz

Submission #1120794

# Submission time Handle Problem Language Result Execution time Memory
1120794 2024-11-28T09:00:12 Z coolboy19521 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 667 ms 143864 KB 
#include"bits/stdc++.h"
using namespace std;
 
const int mxN = 4003;
 
int cl[mxN][mxN];
int g[mxN][mxN];
int H, W;
 
int legal(int i, int j) {
    return 0 <= i && 0 <= j && i < H && j < W && 2 != g[i][j];
}
 
main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> H >> W;
 
    for (int i = 0; i < H; i ++) {
        for (int j = 0; j < W; j ++) {
            char c;
            cin >> c;
            if ('F' == c) {
                g[i][j] = 1;
            } else if ('.' == c) {
                g[i][j] = 2;
            }
        }
    }
 
    deque<pair<int,int>> pq;
    pq.emplace_back(0, 0);
    cl[0][0] = -1;
 
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    int ans = -1;
 
    while (!pq.empty()) {
        auto [i, j] = pq.front();
        pq.pop_front();
        for (int k = 0; k < 4; k ++) {
            int l = i + dx[k];
            int o = j + dy[k];
            if (legal(l, o) && 0 == cl[l][o]) {
                if (g[l][o] == g[i][j]) {
                    cl[l][o] = cl[i][j];
                    pq.emplace_front(l, o);
                } else {
                    cl[l][o] = cl[i][j] - 1;
                    ans = min(ans, cl[l][o]);
                    pq.emplace_back(l, o);
                }
            }
        }
    }
 
    cout << -ans << endl;
}

Compilation message

tracks.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main() {
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6224 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 10 ms 5712 KB Output is correct
5 Correct 6 ms 3340 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 5 ms 2792 KB Output is correct
11 Correct 3 ms 2384 KB Output is correct
12 Correct 6 ms 3408 KB Output is correct
13 Correct 5 ms 3408 KB Output is correct
14 Correct 4 ms 3408 KB Output is correct
15 Correct 13 ms 6156 KB Output is correct
16 Correct 15 ms 6228 KB Output is correct
17 Correct 13 ms 5968 KB Output is correct
18 Correct 9 ms 5712 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31312 KB Output is correct
2 Correct 70 ms 19848 KB Output is correct
3 Correct 347 ms 107308 KB Output is correct
4 Correct 125 ms 43848 KB Output is correct
5 Correct 240 ms 79928 KB Output is correct
6 Correct 667 ms 138964 KB Output is correct
7 Correct 26 ms 32848 KB Output is correct
8 Correct 21 ms 31312 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 30 ms 32252 KB Output is correct
12 Correct 3 ms 1616 KB Output is correct
13 Correct 57 ms 19852 KB Output is correct
14 Correct 33 ms 13392 KB Output is correct
15 Correct 45 ms 16080 KB Output is correct
16 Correct 25 ms 7752 KB Output is correct
17 Correct 159 ms 40840 KB Output is correct
18 Correct 111 ms 47688 KB Output is correct
19 Correct 99 ms 43860 KB Output is correct
20 Correct 78 ms 35968 KB Output is correct
21 Correct 220 ms 79944 KB Output is correct
22 Correct 167 ms 79712 KB Output is correct
23 Correct 275 ms 66748 KB Output is correct
24 Correct 232 ms 76872 KB Output is correct
25 Correct 372 ms 125720 KB Output is correct
26 Correct 450 ms 107200 KB Output is correct
27 Correct 459 ms 143864 KB Output is correct
28 Correct 660 ms 138856 KB Output is correct
29 Correct 540 ms 136600 KB Output is correct
30 Correct 566 ms 135904 KB Output is correct
31 Correct 484 ms 100936 KB Output is correct
32 Correct 553 ms 141868 KB Output is correct