Submission #969837

#	Time	Username	Problem	Language	Result	Execution time	Memory
969837		starchan	Tracks in the Snow (BOI13_tracks)	C++17	75.83 / 100	498 ms	116236 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int LMX = 2e7;
const int INF = LMX+1e5;

char g[LMX]; int n, m;
vector<int> d(LMX, INF);

signed main()
{
	fast();
	cin >> n >> m;
	vector<int> dt = {+m, -m, +1, -1}; 
	for(int i = 0; i < m*n; i++)
		cin >> g[i];
	deque<int> pq;
	pq.pf(0); d[0] = 0;
	while(pq.size())
	{
		int u = pq.front(); pq.pof();
		for(auto x: dt)
		{
			int v = u+x;
			if(v < 0 || (v >= (n*m)) || (g[v] == '.'))
				continue;
			int cn = (g[u] != g[v]); 
			if(d[v] > (d[u]+cn))
			{
				d[v] = d[u]+cn;
				if(cn)
					pq.pb(v);
				else
					pq.pf(v);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n*m; i++)
	{
		if(g[i] != '.')
			ans = max(ans, ++d[i]);
	}
	cout << ans << "\n";
	return 0;
}	

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