Submission #1256639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256639		kerem	Tracks in the Snow (BOI13_tracks)	C++20	84.69 / 100	2102 ms	190716 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 1000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;



void solve(){
	int n,m;
	cin >> n >> m;
	char a[n][m];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin >> a[i][j];
	priority_queue<tiii,vector<tiii>,greater<tiii>> pq;
	pq.push({1,0,0});
	int d[n][m],ans=0;
	memset(d,-1,sizeof(d));
	while(!pq.empty()){
		int x,y,val;
		tie(val,x,y)=pq.top();
		pq.pop();
		if(d[x][y]!=-1) continue;
		d[x][y]=val;
		ans=max(ans,val);
		if(x!=n-1 && a[x+1][y]!='.' && d[x+1][y]==-1)
			pq.push({val+(a[x+1][y]!=a[x][y]),x+1,y});
		if(x!=0 && a[x-1][y]!='.' && d[x-1][y]==-1)
			pq.push({val+(a[x-1][y]!=a[x][y]),x-1,y});
		if(y!=m-1 && a[x][y+1]!='.' && d[x][y+1]==-1)
			pq.push({val+(a[x][y+1]!=a[x][y]),x,y+1});
		if(y!=0 && a[x][y-1]!='.' && d[x][y-1]==-1)
			pq.push({val+(a[x][y-1]!=a[x][y]),x,y-1});
	}
	cout << ans << endl;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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