Submission #961998

#	Time	Username	Problem	Language	Result	Execution time	Memory
961998		pcc	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	494 ms	163584 KiB

tracks

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

const int mxn = 4040;
int N,M;
string arr[mxn];
int dist[mxn][mxn];
deque<tiii> dq;
pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dist,-1,sizeof(dist));
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		arr[i] = "."+arr[i]+".";
	}
	arr[0] = arr[N+1] = string(M+2,'.');
	dist[1][1] = 1;
	dq.push_back(tiii(1,1,1));
	while(!dq.empty()){
		auto [r,c,d] = dq.front();
		dq.pop_front();
		if(dist[r][c] != d)continue;
		for(auto &dd:dir){
			int nr = r+dd.fs,nc = c+dd.sc;
			if(arr[nr][nc] == '.')continue;
			int nd = d+(arr[nr][nc] != arr[r][c]);
			if(dist[nr][nc] == -1||dist[nr][nc]>nd){
				dist[nr][nc] = nd;
				if(nd != d)dq.push_back(tiii(nr,nc,dist[nr][nc]));
				else dq.push_front(tiii(nr,nc,dist[nr][nc]));
			}
		}
	}
	int ans = 0;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)ans = max(ans,dist[i][j]);
	}
	cout<<ans<<'\n';
	return 0;
}

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