Submission #716377

#	Time	Username	Problem	Language	Result	Execution time	Memory
716377		S2speed	Tracks in the Snow (BOI13_tracks)	C++17	71.56 / 100	1394 ms	1048576 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;

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

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

	int n , m;
	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;
			if(i > 0){
				if(a[i - 1][j] != '.'){
					adj[v][a[i - 1][j] != a[0][0]].push_back(v - m);
				}
			}
			if(j > 0){
				if(a[i][j - 1] != '.'){
					adj[v][a[i][j - 1] != a[0][0]].push_back(v - 1);
				}
			}
			if(i < n - 1){
				if(a[i + 1][j] != '.'){
					adj[v][a[i + 1][j] != a[0][0]].push_back(v + m);
				}
			}
			if(j < m - 1){
				if(a[i][j + 1] != '.'){
					adj[v][a[i][j + 1] != a[0][0]].push_back(v + 1);
				}
			}
		}
	}
	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++];
			for(auto i : adj[v][j & 1]){
				if(mark[i]) continue;
				mark[i] = true;
				f.push_back(i);
				g.push_back(i);
			}
		}
		f = g;
		g.clear();
	}
	cout<<ans<<'\n';
	return 0;
}

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