oj.uz

Submission #46595

# Submission time Handle Problem Language Result Execution time Memory
46595 2018-04-21T19:55:11 Z Bruteforceman Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 949 ms 316896 KB 
#include "bits/stdc++.h"
using namespace std;
char a[4001][4001];
int d[4001][4001];
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
int N, M;
typedef pair <int, int> pii;
const int inf = 1e9;

bool inside(int x, int y) {
	return (0 <= x && x < N) && (0 <= y && y < M);
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &N, &M);
	for(int i = 0; i < N; i++) {
		scanf("%s", a[i]);
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			d[i][j] = inf;
		}
	}
	deque <pii> Q;
	Q.push_front(pii(N - 1, M - 1));
	d[N - 1][M - 1] = 0;

	while(!Q.empty()) {
		pii c = Q.front();
		Q.pop_front();
		for(int i = 0; i < 4; i++) {
			int p = c.first + dx[i];
			int q = c.second + dy[i];
			if(inside(p, q) && a[p][q] != '.') {
				int w = (a[c.first][c.second] != a[p][q]);
				if(d[p][q] > w + d[c.first][c.second]) {
					d[p][q] = w + d[c.first][c.second];
					if(w) Q.push_back(pii(p, q));
					else Q.push_front(pii(p, q));
				} 
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if(a[i][j] != '.') {
				ans = max(ans, d[i][j]);
			}
		}
	}
	printf("%d\n", ans + 1);
	return 0;
}

Compilation message

tracks.cpp: In function 'int main(int, const char**)':
tracks.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5368 KB Output is correct
2 Correct 2 ms 5368 KB Output is correct
3 Correct 2 ms 5368 KB Output is correct
4 Correct 10 ms 5680 KB Output is correct
5 Correct 5 ms 5680 KB Output is correct
6 Correct 2 ms 5680 KB Output is correct
7 Correct 2 ms 5680 KB Output is correct
8 Correct 2 ms 5680 KB Output is correct
9 Correct 2 ms 5680 KB Output is correct
10 Correct 5 ms 5680 KB Output is correct
11 Correct 5 ms 5680 KB Output is correct
12 Correct 7 ms 5680 KB Output is correct
13 Correct 5 ms 5680 KB Output is correct
14 Correct 5 ms 5680 KB Output is correct
15 Correct 14 ms 6768 KB Output is correct
16 Correct 16 ms 7032 KB Output is correct
17 Correct 13 ms 7032 KB Output is correct
18 Correct 13 ms 7380 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33092 KB Output is correct
2 Correct 53 ms 33092 KB Output is correct
3 Correct 267 ms 98204 KB Output is correct
4 Correct 95 ms 98204 KB Output is correct
5 Correct 164 ms 98204 KB Output is correct
6 Correct 937 ms 139404 KB Output is correct
7 Correct 24 ms 139404 KB Output is correct
8 Correct 22 ms 139404 KB Output is correct
9 Correct 5 ms 139404 KB Output is correct
10 Correct 3 ms 139404 KB Output is correct
11 Correct 22 ms 139404 KB Output is correct
12 Correct 3 ms 139404 KB Output is correct
13 Correct 54 ms 139404 KB Output is correct
14 Correct 30 ms 139404 KB Output is correct
15 Correct 27 ms 139404 KB Output is correct
16 Correct 24 ms 139404 KB Output is correct
17 Correct 135 ms 139404 KB Output is correct
18 Correct 109 ms 139404 KB Output is correct
19 Correct 92 ms 139404 KB Output is correct
20 Correct 70 ms 139404 KB Output is correct
21 Correct 172 ms 139404 KB Output is correct
22 Correct 163 ms 143892 KB Output is correct
23 Correct 247 ms 143892 KB Output is correct
24 Correct 161 ms 161816 KB Output is correct
25 Correct 526 ms 195548 KB Output is correct
26 Correct 838 ms 247964 KB Output is correct
27 Correct 853 ms 247964 KB Output is correct
28 Correct 870 ms 251960 KB Output is correct
29 Correct 949 ms 266440 KB Output is correct
30 Correct 848 ms 285584 KB Output is correct
31 Correct 561 ms 285584 KB Output is correct
32 Correct 798 ms 316896 KB Output is correct