oj.uz

Submission #850167

# Submission time Handle Problem Language Result Execution time Memory
850167 2023-09-15T22:59:00 Z NK_ Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 550 ms 137256 KB 
#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define pi pair<int, int>
#define se second
#define fi first
#define vt vector
#define pb push_back
#define nl endl

#define dbg(...) " [" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
#define all(v) v.begin(), v.end()
#define FORN(a, b, i) for(int i = (a); i < (b); i++)
#define FORE(a, b, i) for(int i = (a); i <= (b); i++)
#define FOR(a, i) for(int i = 0; i < (a); i++)
#define trav(x, a) for (auto& a : x)

using namespace std;

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (name.empty()) return;
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}


const int nax = 4000;
string b[nax];
int dep[nax][nax];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
int n, m;
bool inside(int x, int y) {
	return (x >= 0 && x < n && y >= 0 && y < m && b[x][y] != '.');
}

int main() {


	memset(dep, -1, sizeof(dep));

	cin >> n >> m;
	FOR(n, i) cin >> b[i];

	deque<pair<int, int>> d;
	dep[0][0] = 1;
	d.push_back({0, 0});
	int ans = 0;
	while(!d.empty()) {
		pi u = d.front();
		d.pop_front();
		ans = max(ans, dep[u.fi][u.se]);
		FOR(4, i) {
			pi v = {u.fi+dx[i], u.se+dy[i]};
			if (inside(v.fi, v.se) && dep[v.fi][v.se] == -1) {
				if (b[v.fi][v.se] == b[u.fi][u.se]) {
					dep[v.fi][v.se] = dep[u.fi][u.se];
					d.push_front(v);
				} else {
					dep[v.fi][v.se] = dep[u.fi][u.se]+1;
					d.push_back(v);
				}
			}
		}
	}
	cout << ans << endl;
    
    return 0;
}

Compilation message

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 63832 KB Output is correct
2 Correct 8 ms 63068 KB Output is correct
3 Correct 8 ms 63020 KB Output is correct
4 Correct 13 ms 63580 KB Output is correct
5 Correct 10 ms 63288 KB Output is correct
6 Correct 8 ms 63068 KB Output is correct
7 Correct 7 ms 62944 KB Output is correct
8 Correct 8 ms 63068 KB Output is correct
9 Correct 8 ms 63068 KB Output is correct
10 Correct 9 ms 63324 KB Output is correct
11 Correct 9 ms 63324 KB Output is correct
12 Correct 11 ms 63312 KB Output is correct
13 Correct 10 ms 63324 KB Output is correct
14 Correct 11 ms 63320 KB Output is correct
15 Correct 17 ms 63836 KB Output is correct
16 Correct 18 ms 63836 KB Output is correct
17 Correct 15 ms 63808 KB Output is correct
18 Correct 13 ms 63580 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 63064 KB Output is correct
2 Correct 49 ms 66908 KB Output is correct
3 Correct 318 ms 106832 KB Output is correct
4 Correct 87 ms 73856 KB Output is correct
5 Correct 201 ms 82324 KB Output is correct
6 Correct 548 ms 121012 KB Output is correct
7 Correct 10 ms 63064 KB Output is correct
8 Correct 9 ms 63068 KB Output is correct
9 Correct 9 ms 63380 KB Output is correct
10 Correct 8 ms 63068 KB Output is correct
11 Correct 9 ms 63064 KB Output is correct
12 Correct 8 ms 63068 KB Output is correct
13 Correct 49 ms 66908 KB Output is correct
14 Correct 31 ms 65628 KB Output is correct
15 Correct 29 ms 65948 KB Output is correct
16 Correct 27 ms 64592 KB Output is correct
17 Correct 114 ms 74576 KB Output is correct
18 Correct 92 ms 74324 KB Output is correct
19 Correct 85 ms 73856 KB Output is correct
20 Correct 77 ms 73044 KB Output is correct
21 Correct 193 ms 83104 KB Output is correct
22 Correct 181 ms 82260 KB Output is correct
23 Correct 223 ms 79544 KB Output is correct
24 Correct 191 ms 82744 KB Output is correct
25 Correct 400 ms 106836 KB Output is correct
26 Correct 351 ms 137256 KB Output is correct
27 Correct 452 ms 120212 KB Output is correct
28 Correct 550 ms 121056 KB Output is correct
29 Correct 546 ms 119288 KB Output is correct
30 Correct 496 ms 121568 KB Output is correct
31 Correct 413 ms 84500 KB Output is correct
32 Correct 426 ms 121152 KB Output is correct