Submission #649071

#	Time	Username	Problem	Language	Result	Execution time	Memory
649071		rickbaishuak	Tracks in the Snow (BOI13_tracks)	C++14	82.50 / 100	2145 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
#define pb push_back
#define er erase
#define in insert
#define s(a, x, y) sort(a.begin()+x, a.begin()+y);
#define r(a, x, y) reverse(a.begin()+x, a.begin()+y);
#define mp make_pair
#define F first
#define S second
#define ll long long
#define ld long double
#define forn(i, a, b) for(int i=a; i<=b; i++)
#define form(i, a, b) for(int i=a; i>=b; i--)
#define PI 3.14159265358979
#define inf 2147483647
#define sp setprecision
#define pii pair <int, int>
#define gcd __gcd
#define endl '\n'
#define sz(a) (int)a.size()
using namespace std;
const ll N = 4000 + 13;
ll t1, n, m, d[N][N], ans;
vector <pii> g[N][N];
string t;
char s[N][N];
deque <pii> q;
bool st1[N][N], st2[N][N];
pii v;
void solve(){
	cin >> n >> m;
	forn (i, 1, n){
		cin >> t;
		forn (j, 1, m){
			s[i][j] = t[j - 1];
			if (i > 1 && s[i][j] != '.' && s[i - 1][j] != '.') {
				g[i][j].pb ({i - 1, j});
				g[i - 1][j].pb ({i, j});
				if (s[i][j] == s[i - 1][j]) st2[i][j] = 0;
				else st2[i][j] = 1;
			}
			if (j > 1 && s[i][j] != '.' && s[i][j - 1] != '.') {
				g[i][j].pb ({i, j - 1});
				g[i][j - 1].pb ({i, j});
				if (s[i][j] == s[i][j - 1]) st1[i][j] = 0;
				else st1[i][j] = 1;
			}
		}
	}
	q.push_back ({1, 1});
	d[1][1] = 1;
	while (q.size()){
		v = q[0];
		q.pop_front();
		for (pii to: g[v.F][v.S]){
			if (!d[to.F][to.S]){
				d[to.F][to.S] = d[v.F][v.S];
				if (v.F == to.F && !st1[v.F][max (v.S, to.S)] || v.S == to.S && !st2[max (v.F, to.F)][v.S]) q.push_front (to);
				else {
					q.push_back (to);
					d[to.F][to.S] ++;
				}
				ans = max (ans, d[to.F][to.S]);
			}
		}
	}
//	forn (i, 1, n){
//		forn (j, 1, m){
//			cout << d[i][j];
//		}
//		cout << endl;
//	}
	cout << ans << endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
//	cin >> t1;
	t1 = 1;
	while (t1 --){
		solve();
	}
	return 0;
}
/*
5
0.50 0.29 0.49 0.95 0.66
2 3
0 3
3 4
2 1

5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
1
4 0.66
*/

Compilation message (stderr)

tracks.cpp: In function 'void solve()':
tracks.cpp:58:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |     if (v.F == to.F && !st1[v.F][max (v.S, to.S)] || v.S == to.S && !st2[max (v.F, to.F)][v.S]) q.push_front (to);
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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