oj.uz

Submission #371004

# Submission time Handle Problem Language Result Execution time Memory
371004 2021-02-25T13:52:39 Z XEMPLI5 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1369 ms 143356 KB 
#include <bits/stdc++.h>
using namespace std;

int h,w, mxH = 4e3;
vector<vector<char>> grid(mxH, vector<char> (mxH));
vector<vector<int>> dis(mxH, vector<int> (mxH, 1e9));
vector<int> dx = {0,1,0,-1}, dy = {1,0,-1,0};
vector<vector<bool>> vis(mxH, vector<bool> (mxH));

bool check(int x, int y){
	return x >= 0 && x < h && y >= 0 && y < w && grid[x][y] != '.';
}

bool calcW(int x, int y, int nx ,int ny){
	return grid[x][y] != grid[nx][ny];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> h >> w;
	for(int i=0; i<h; i++)
		for(int j=0; j<w; j++) cin >> grid[i][j];
	
	deque<pair<int,int>> dq;
	dq.push_front({0,0});
	dis[0][0] = 1;
	while(dq.size()){
		int x = dq.front().first, y = dq.front().second; dq.pop_front();
		if(vis[x][y]) continue;
		vis[x][y] = true;
		for(int i=0; i<4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if(check(nx,ny) && dis[nx][ny] > dis[x][y] + calcW(x,y,nx,ny)){
				dis[nx][ny] = dis[x][y] + calcW(x,y,nx,ny);
				if(calcW(x,y,nx,ny))
					dq.push_back({nx,ny});
				else dq.push_front({nx,ny});
			}
		}
	}
	int ans = 0;
	for(int i=0; i<h; i++)
		for(int j=0; j<w; j++) if(dis[i][j] != 1e9) ans = max(dis[i][j], ans);
	
	cout << ans << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 81388 KB Output is correct
2 Correct 49 ms 81132 KB Output is correct
3 Correct 46 ms 81152 KB Output is correct
4 Correct 57 ms 81516 KB Output is correct
5 Correct 50 ms 81132 KB Output is correct
6 Correct 48 ms 81132 KB Output is correct
7 Correct 53 ms 81132 KB Output is correct
8 Correct 47 ms 81132 KB Output is correct
9 Correct 46 ms 81132 KB Output is correct
10 Correct 52 ms 81132 KB Output is correct
11 Correct 49 ms 81260 KB Output is correct
12 Correct 53 ms 81260 KB Output is correct
13 Correct 53 ms 81260 KB Output is correct
14 Correct 49 ms 81168 KB Output is correct
15 Correct 73 ms 81408 KB Output is correct
16 Correct 75 ms 81388 KB Output is correct
17 Correct 59 ms 81388 KB Output is correct
18 Correct 57 ms 81516 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 81152 KB Output is correct
2 Correct 122 ms 82600 KB Output is correct
3 Correct 534 ms 96748 KB Output is correct
4 Correct 186 ms 84716 KB Output is correct
5 Correct 371 ms 89964 KB Output is correct
6 Correct 1339 ms 111340 KB Output is correct
7 Correct 51 ms 81132 KB Output is correct
8 Correct 48 ms 81132 KB Output is correct
9 Correct 49 ms 81260 KB Output is correct
10 Correct 47 ms 81132 KB Output is correct
11 Correct 47 ms 81132 KB Output is correct
12 Correct 47 ms 81132 KB Output is correct
13 Correct 122 ms 82668 KB Output is correct
14 Correct 90 ms 82156 KB Output is correct
15 Correct 84 ms 82028 KB Output is correct
16 Correct 79 ms 81772 KB Output is correct
17 Correct 250 ms 85120 KB Output is correct
18 Correct 197 ms 84972 KB Output is correct
19 Correct 180 ms 84844 KB Output is correct
20 Correct 153 ms 84588 KB Output is correct
21 Correct 341 ms 90220 KB Output is correct
22 Correct 373 ms 89964 KB Output is correct
23 Correct 442 ms 88940 KB Output is correct
24 Correct 330 ms 90092 KB Output is correct
25 Correct 807 ms 96876 KB Output is correct
26 Correct 1308 ms 143356 KB Output is correct
27 Correct 1369 ms 122656 KB Output is correct
28 Correct 1313 ms 111196 KB Output is correct
29 Correct 1318 ms 108352 KB Output is correct
30 Correct 1330 ms 115444 KB Output is correct
31 Correct 975 ms 91628 KB Output is correct
32 Correct 1304 ms 120992 KB Output is correct