Submission #371004

#	Time	Username	Problem	Language	Result	Execution time	Memory
371004		XEMPLI5	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1369 ms	143356 KiB

tracks

#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 / 30
• Subtask 2: 70 / 70