oj.uz

Submission #415977

# Submission time Handle Problem Language Result Execution time Memory
415977 2021-06-01T18:46:43 Z nkato Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 931 ms 128300 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 41 ms 63692 KB Output is correct
2 Correct 31 ms 62972 KB Output is correct
3 Correct 32 ms 62992 KB Output is correct
4 Correct 39 ms 63508 KB Output is correct
5 Correct 31 ms 63176 KB Output is correct
6 Correct 28 ms 63016 KB Output is correct
7 Correct 28 ms 63044 KB Output is correct
8 Correct 32 ms 63052 KB Output is correct
9 Correct 29 ms 63028 KB Output is correct
10 Correct 30 ms 63152 KB Output is correct
11 Correct 30 ms 63136 KB Output is correct
12 Correct 32 ms 63184 KB Output is correct
13 Correct 32 ms 63184 KB Output is correct
14 Correct 37 ms 63172 KB Output is correct
15 Correct 40 ms 63740 KB Output is correct
16 Correct 48 ms 63724 KB Output is correct
17 Correct 39 ms 63612 KB Output is correct
18 Correct 39 ms 63560 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63044 KB Output is correct
2 Correct 111 ms 66500 KB Output is correct
3 Correct 541 ms 94016 KB Output is correct
4 Correct 169 ms 71244 KB Output is correct
5 Correct 327 ms 76924 KB Output is correct
6 Correct 931 ms 109372 KB Output is correct
7 Correct 32 ms 62988 KB Output is correct
8 Correct 33 ms 63056 KB Output is correct
9 Correct 34 ms 63172 KB Output is correct
10 Correct 32 ms 63040 KB Output is correct
11 Correct 36 ms 63044 KB Output is correct
12 Correct 33 ms 63060 KB Output is correct
13 Correct 96 ms 66472 KB Output is correct
14 Correct 70 ms 65628 KB Output is correct
15 Correct 71 ms 65888 KB Output is correct
16 Correct 67 ms 64408 KB Output is correct
17 Correct 216 ms 71872 KB Output is correct
18 Correct 176 ms 71620 KB Output is correct
19 Correct 167 ms 71292 KB Output is correct
20 Correct 143 ms 70724 KB Output is correct
21 Correct 322 ms 77232 KB Output is correct
22 Correct 320 ms 76900 KB Output is correct
23 Correct 357 ms 75124 KB Output is correct
24 Correct 329 ms 77292 KB Output is correct
25 Correct 715 ms 94980 KB Output is correct
26 Correct 567 ms 128300 KB Output is correct
27 Correct 777 ms 108412 KB Output is correct
28 Correct 858 ms 109168 KB Output is correct
29 Correct 919 ms 107400 KB Output is correct
30 Correct 841 ms 110036 KB Output is correct
31 Correct 771 ms 77592 KB Output is correct
32 Correct 697 ms 109068 KB Output is correct