oj.uz

Submission #724391

# Submission time Handle Problem Language Result Execution time Memory
724391 2023-04-15T07:27:57 Z chanhchuong123 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 773 ms 138752 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};

const int MAX = 4000;
int n, m;
int ans = 0;
int d[MAX][MAX];
char a[MAX][MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    memset(d, 0x3f, sizeof d);
    deque<pair<int, int>> dq;
    dq.push_front({0, 0});
    d[0][0] = 1;
    while (dq.size()) {
        int u = dq.front().fi;
        int v = dq.front().se;
        maximize(ans, d[u][v]);
        dq.pop_front();

        for (int i = 0; i < 4; ++i) {
            int x = u + dx[i], y = v + dy[i];
            if (x < 0 || x >= n) continue;
            if (y < 0 || y >= m) continue;
            if (a[x][y] != '.') {
                int w = a[u][v] != a[x][y];
                if (minimize(d[x][y], d[u][v] + w)) {
                    if (w) dq.push_back({x, y});
                    else dq.push_front({x, y});
                }
            }
        }
    }
    cout << ans;
	return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 65140 KB Output is correct
2 Correct 27 ms 62924 KB Output is correct
3 Correct 35 ms 63092 KB Output is correct
4 Correct 35 ms 65208 KB Output is correct
5 Correct 28 ms 64076 KB Output is correct
6 Correct 26 ms 62988 KB Output is correct
7 Correct 26 ms 63044 KB Output is correct
8 Correct 28 ms 63188 KB Output is correct
9 Correct 26 ms 63308 KB Output is correct
10 Correct 30 ms 63928 KB Output is correct
11 Correct 32 ms 63820 KB Output is correct
12 Correct 34 ms 64100 KB Output is correct
13 Correct 33 ms 64084 KB Output is correct
14 Correct 31 ms 64076 KB Output is correct
15 Correct 40 ms 65092 KB Output is correct
16 Correct 42 ms 65108 KB Output is correct
17 Correct 40 ms 65012 KB Output is correct
18 Correct 36 ms 65168 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 77896 KB Output is correct
2 Correct 79 ms 69260 KB Output is correct
3 Correct 357 ms 94272 KB Output is correct
4 Correct 113 ms 73980 KB Output is correct
5 Correct 222 ms 83368 KB Output is correct
6 Correct 773 ms 109344 KB Output is correct
7 Correct 31 ms 78568 KB Output is correct
8 Correct 31 ms 77908 KB Output is correct
9 Correct 28 ms 62976 KB Output is correct
10 Correct 26 ms 62912 KB Output is correct
11 Correct 32 ms 78292 KB Output is correct
12 Correct 28 ms 63440 KB Output is correct
13 Correct 76 ms 69332 KB Output is correct
14 Correct 54 ms 67280 KB Output is correct
15 Correct 52 ms 67820 KB Output is correct
16 Correct 47 ms 65100 KB Output is correct
17 Correct 152 ms 74808 KB Output is correct
18 Correct 125 ms 74576 KB Output is correct
19 Correct 110 ms 73852 KB Output is correct
20 Correct 101 ms 73052 KB Output is correct
21 Correct 218 ms 84168 KB Output is correct
22 Correct 241 ms 83532 KB Output is correct
23 Correct 264 ms 80324 KB Output is correct
24 Correct 220 ms 84108 KB Output is correct
25 Correct 467 ms 94220 KB Output is correct
26 Correct 522 ms 138752 KB Output is correct
27 Correct 686 ms 134884 KB Output is correct
28 Correct 764 ms 109420 KB Output is correct
29 Correct 763 ms 106660 KB Output is correct
30 Correct 718 ms 111032 KB Output is correct
31 Correct 530 ms 86028 KB Output is correct
32 Correct 625 ms 117256 KB Output is correct