Submission #716378

#	Time	Username	Problem	Language	Result	Execution time	Memory
716378		S2speed	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1896 ms	160492 KiB

tracks

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 4e3 + 17 , maxv = 16e6 + 17 , md = 1e9 + 7 , inf = 2e16;

int n , m;
vector<int> adj , f , g;
char a[maxn][maxn];
bool mark[maxv];

void bruh(ll v , bool t){
	int i = v / m , j = v % m;
	adj.clear();
	if(i > 0){
		if(a[i - 1][j] != '.'){
			if((a[i - 1][j] != a[0][0]) == t) adj.push_back(v - m);
		}
	}
	if(j > 0){
		if(a[i][j - 1] != '.'){
			if((a[i][j - 1] != a[0][0]) == t) adj.push_back(v - 1);
		}
	}
	if(i < n - 1){
		if(a[i + 1][j] != '.'){
			if((a[i + 1][j] != a[0][0]) == t) adj.push_back(v + m);
		}
	}
	if(j < m - 1){
		if(a[i][j + 1] != '.'){
			if((a[i][j + 1] != a[0][0]) == t) adj.push_back(v + 1);
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin>>n>>m;
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			cin>>a[i][j];
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			int v = i * m + j;
			
		}
	}
	int lm = n * m - 1;
	mark[0] = mark[lm] = true;
	f.push_back(0); f.push_back(lm);
	g.push_back(0); g.push_back(lm);
	int ans;
	for(int j = 0 ; ; j++){
		if(f.empty()){
			ans = j - 1;
			break;
		}
		int x = 0;
		while(x < sze(f)){
			int v = f[x++];
			bruh(v , j & 1);
			for(auto i : adj){
				if(mark[i]) continue;
				mark[i] = true;
				f.push_back(i);
				g.push_back(i);
			}
		}
		f = g;
		g.clear();
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:63:8: warning: unused variable 'v' [-Wunused-variable]
   63 |    int v = i * m + j;
      |        ^

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