oj.uz

Submission #25840

# Submission time Handle Problem Language Result Execution time Memory
25840 2017-06-24T09:42:12 Z gs14004 Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 1816 ms 454416 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

queue<pi> q1, q2;

int n, m, ret;
char str[4005][4005];
bool vis[4005][4005];

void bfs(queue<pi> &q1, queue<pi> &q2, int d){
	if(q1.empty()) return;
	ret = d;
	while(!q1.empty()){
		pi x = q1.front();
		q1.pop();
		for(int i=0; i<4; i++){
			if(x.first + dx[i] < 0 || x.second + dy[i] < 0 || x.first + dx[i] >= n || x.second + dy[i] >= m){
				continue;
			}
			if(vis[x.first+dx[i]][x.second+dy[i]] || str[x.first+dx[i]][x.second+dy[i]] == '.') continue;
			vis[x.first+dx[i]][x.second+dy[i]] = 1;
			if(str[x.first + dx[i]][x.second + dy[i]] != str[x.first][x.second]) q2.push(pi(x.first + dx[i], x.second + dy[i]));
			else q1.push(pi(x.first + dx[i], x.second + dy[i]));
		}
	}
	bfs(q2, q1, d+1);
}

int main(){
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> str[i];
	q1.push(pi(0, 0));
	vis[0][0] = 1;
	bfs(q1, q2, 1);
	cout << ret;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33480 KB Output is correct
2 Correct 0 ms 33348 KB Output is correct
3 Correct 0 ms 33348 KB Output is correct
4 Correct 13 ms 33480 KB Output is correct
5 Correct 3 ms 33348 KB Output is correct
6 Correct 0 ms 33348 KB Output is correct
7 Correct 0 ms 33348 KB Output is correct
8 Correct 0 ms 33348 KB Output is correct
9 Correct 0 ms 33348 KB Output is correct
10 Correct 3 ms 33348 KB Output is correct
11 Correct 3 ms 33348 KB Output is correct
12 Correct 3 ms 33348 KB Output is correct
13 Correct 6 ms 33348 KB Output is correct
14 Correct 6 ms 33348 KB Output is correct
15 Correct 23 ms 33348 KB Output is correct
16 Correct 16 ms 33480 KB Output is correct
17 Correct 16 ms 33348 KB Output is correct
18 Correct 13 ms 33480 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33700 KB Output is correct
2 Correct 116 ms 33348 KB Output is correct
3 Correct 806 ms 88528 KB Output is correct
4 Correct 193 ms 33348 KB Output is correct
5 Correct 586 ms 454412 KB Output is correct
6 Correct 1636 ms 43596 KB Output is correct
7 Correct 6 ms 33640 KB Output is correct
8 Correct 0 ms 33700 KB Output is correct
9 Correct 3 ms 33348 KB Output is correct
10 Correct 0 ms 33460 KB Output is correct
11 Correct 6 ms 33424 KB Output is correct
12 Correct 0 ms 34256 KB Output is correct
13 Correct 106 ms 33348 KB Output is correct
14 Correct 46 ms 33348 KB Output is correct
15 Correct 49 ms 46572 KB Output is correct
16 Correct 49 ms 33348 KB Output is correct
17 Correct 326 ms 33544 KB Output is correct
18 Correct 286 ms 84864 KB Output is correct
19 Correct 219 ms 33348 KB Output is correct
20 Correct 199 ms 44504 KB Output is correct
21 Correct 486 ms 64196 KB Output is correct
22 Correct 566 ms 454416 KB Output is correct
23 Correct 683 ms 33736 KB Output is correct
24 Correct 533 ms 173524 KB Output is correct
25 Correct 1096 ms 246752 KB Output is correct
26 Correct 1169 ms 33348 KB Output is correct
27 Correct 1376 ms 35040 KB Output is correct
28 Correct 1619 ms 43596 KB Output is correct
29 Correct 1816 ms 42092 KB Output is correct
30 Correct 1553 ms 41368 KB Output is correct
31 Correct 1189 ms 33744 KB Output is correct
32 Correct 1366 ms 34140 KB Output is correct