oj.uz

Submission #134498

# Submission time Handle Problem Language Result Execution time Memory
134498 2019-07-22T22:13:25 Z wzy Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 863 ms 118916 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp mka
string s[4005];
int dist[4005][4005];
deque<pair<int, int> > dq;
int h , w;
int dx[4] = { 0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	cin>>h>>w;
	for(int i = 0 ; i < h ; i ++){
		cin>>s[i];
		for(int j = 0 ; j  < w ; j ++){
			dist[i][j] = numeric_limits<int>::max() ;
			dist[i][j]--;
		}
	}
	dq.push_back(pair<int,int>(0,0));
	int ans = 0;
	dist[0][0] = 0;
	while(!dq.empty()){
		pii u = dq.front();
		ans = max(ans , dist[u.first][u.second]+1);
		dq.pop_front();
		for(int i = 0 ; i < 4 ; i++){
			int x = u.first + dx[i] , y = u.second + dy[i];
			if(x >= 0 && y >= 0 && x < h && y < w){
				if(s[x][y] != s[u.first][u.second] && s[x][y] != '.' && dist[x][y] > (dist[u.first][u.second] + 1)){
					dist[x][y] = dist[u.first][u.second] + 1;
					dq.push_back(pair<int,int>(x,y));
				}
				else{
					if(s[x][y] == s[u.first][u.second] && dist[x][y] > (dist[u.first][u.second])){
						dist[x][y] = dist[u.first][u.second];
						dq.push_front(pair<int,int>(x,y));
					}
				}
			}
		}
	}
	cout<<ans<<"\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3704 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 10 ms 3448 KB Output is correct
5 Correct 5 ms 2040 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 5 ms 1784 KB Output is correct
11 Correct 4 ms 1528 KB Output is correct
12 Correct 9 ms 2168 KB Output is correct
13 Correct 5 ms 2040 KB Output is correct
14 Correct 5 ms 2040 KB Output is correct
15 Correct 17 ms 3704 KB Output is correct
16 Correct 20 ms 3704 KB Output is correct
17 Correct 14 ms 3576 KB Output is correct
18 Correct 10 ms 3508 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15992 KB Output is correct
2 Correct 59 ms 13304 KB Output is correct
3 Correct 277 ms 80920 KB Output is correct
4 Correct 76 ms 26616 KB Output is correct
5 Correct 189 ms 57348 KB Output is correct
6 Correct 809 ms 95328 KB Output is correct
7 Correct 19 ms 16760 KB Output is correct
8 Correct 14 ms 15992 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 14 ms 16504 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 56 ms 13432 KB Output is correct
14 Correct 33 ms 8572 KB Output is correct
15 Correct 23 ms 9464 KB Output is correct
16 Correct 29 ms 5240 KB Output is correct
17 Correct 140 ms 28764 KB Output is correct
18 Correct 94 ms 28280 KB Output is correct
19 Correct 76 ms 26744 KB Output is correct
20 Correct 70 ms 24568 KB Output is correct
21 Correct 170 ms 59128 KB Output is correct
22 Correct 191 ms 57336 KB Output is correct
23 Correct 269 ms 48052 KB Output is correct
24 Correct 157 ms 58232 KB Output is correct
25 Correct 458 ms 80888 KB Output is correct
26 Correct 677 ms 118916 KB Output is correct
27 Correct 690 ms 106664 KB Output is correct
28 Correct 863 ms 95416 KB Output is correct
29 Correct 785 ms 92488 KB Output is correct
30 Correct 752 ms 97956 KB Output is correct
31 Correct 750 ms 62328 KB Output is correct
32 Correct 656 ms 104860 KB Output is correct