Submission #716940

#	Time	Username	Problem	Language	Result	Execution time	Memory
716940		study	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	2120 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

const int N = 4000;

string grid[N];
bool vu[N][N];
bitset<N*N> seen;
int comp[N][N];
vector<int> adj[N*N];
int h,w;

vector<pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};

void dfs(int x, int y, int k, char c){
	if (x < 0 or y < 0 or x >= h or y >= w or vu[x][y] or grid[x][y] != c) return;
	vu[x][y] = true;
	comp[x][y] = k;
	for (auto d:dir){
		int nx = d.first+x, ny = d.second+y;
		dfs(nx,ny,k,c);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> h >> w;
	for (int i=0; i<h; ++i){
		cin >> grid[i];
	}
	int k = 0;
	for (int i=0; i<h; ++i){
		for (int j=0; j<w; ++j){
			if (!vu[i][j]){
				dfs(i,j,k,grid[i][j]);
				++k;
			}
		}
	}
	for (int i=0; i<h; ++i){
		for (int j=0; j<w; ++j){
			for (auto d:dir){
				int nx = d.first+i, ny = d.second+j;
				if (nx >= 0 and ny >= 0 and nx < h and ny < w and comp[nx][ny] != comp[i][j]){
					adj[comp[nx][ny]].emplace_back(comp[i][j]);
					adj[comp[i][j]].emplace_back(comp[nx][ny]);
				}
			}
		}
	}
	deque<pair<int,int>> q;
	q.emplace_back(0,comp[0][0]);
	int ans = 0;
	while (!q.empty()){
		auto f = q.front();
		q.pop_front();
		ans = max(ans,f.first);
		for (auto i:adj[f.second]){
			if (!seen[i]){
				seen[i] = true;
				q.emplace_back(f.first+1,i);
			}
		}
	}
	cout << ans;
	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70