oj.uz

Submission #445073

# Submission time Handle Problem Language Result Execution time Memory
445073 2021-07-16T11:05:05 Z KazamaHoang Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1038 ms 121844 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define bit(x, i) (((x) >> (i)) & 1)
#define sz(x) ((int)x.size())

using namespace std;
using ll = long long;

const int inf = 1061109567;
const ll INF = 4557430888798830399;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, -1, 0};
const int dy[] = {1, 0, 0, -1};

int numRow, numCol;
char snow[4005][4005];
int dist[4005][4005];

bool outSide(int ux, int vy) {
    if (ux == 0 || ux == numRow + 1 || vy == 0 || vy == numCol + 1 || snow[ux][vy] == '.')
        return true;
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    #define Task ""
    if (fopen(Task".in", "r")) {
        freopen(Task".in", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> numRow >> numCol;
    for (int i = 1; i <= numRow; ++ i)
        for (int j = 1; j <= numCol; ++ j)
            cin >> snow[i][j];
    deque <pair <int, int>> dq;
    dq.push_back({1, 1});
    dist[1][1] = 1;
    int res = 1;
    while (!dq.empty()) {
        int u = dq.front().F;
        int v = dq.front().S;
        dq.pop_front();
        res = max(res, dist[u][v]);
        for (int i = 0; i <= 3; ++ i) {
            int ux = u + dx[i];
            int vy = v + dy[i];
            if (outSide(ux, vy) || dist[ux][vy] != 0)
                continue;
            if (snow[ux][vy] == snow[u][v]) {
                dq.push_front({ux, vy});
                dist[ux][vy] = dist[u][v];
            } else {
                dq.push_back({ux, vy});
                dist[ux][vy] = dist[u][v] + 1;
            }
        }
    }
    cout << res;
    return 0;
}

// Written by Kazama Hoang ^^

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(Task".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(Task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5196 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 10 ms 5024 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 4 ms 2380 KB Output is correct
11 Correct 3 ms 2124 KB Output is correct
12 Correct 7 ms 2960 KB Output is correct
13 Correct 4 ms 2892 KB Output is correct
14 Correct 4 ms 2904 KB Output is correct
15 Correct 15 ms 5048 KB Output is correct
16 Correct 16 ms 5200 KB Output is correct
17 Correct 14 ms 4940 KB Output is correct
18 Correct 10 ms 4984 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30796 KB Output is correct
2 Correct 62 ms 13516 KB Output is correct
3 Correct 416 ms 57632 KB Output is correct
4 Correct 115 ms 29016 KB Output is correct
5 Correct 277 ms 44448 KB Output is correct
6 Correct 898 ms 93124 KB Output is correct
7 Correct 19 ms 32204 KB Output is correct
8 Correct 17 ms 30768 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 19 ms 31548 KB Output is correct
12 Correct 2 ms 1484 KB Output is correct
13 Correct 65 ms 13508 KB Output is correct
14 Correct 35 ms 9540 KB Output is correct
15 Correct 35 ms 12072 KB Output is correct
16 Correct 27 ms 5064 KB Output is correct
17 Correct 159 ms 24788 KB Output is correct
18 Correct 139 ms 31720 KB Output is correct
19 Correct 118 ms 28996 KB Output is correct
20 Correct 95 ms 22032 KB Output is correct
21 Correct 246 ms 43476 KB Output is correct
22 Correct 283 ms 44484 KB Output is correct
23 Correct 312 ms 36184 KB Output is correct
24 Correct 243 ms 40760 KB Output is correct
25 Correct 681 ms 78544 KB Output is correct
26 Correct 939 ms 118968 KB Output is correct
27 Correct 919 ms 121844 KB Output is correct
28 Correct 1038 ms 93080 KB Output is correct
29 Correct 900 ms 90364 KB Output is correct
30 Correct 918 ms 97600 KB Output is correct
31 Correct 661 ms 63360 KB Output is correct
32 Correct 983 ms 100984 KB Output is correct