Submission #649074

# Submission time Handle Problem Language Result Execution time Memory
649074 2022-10-09T07:15:58 Z rickbaishuak Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
787 ms 186124 KB
#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, x, y;
ll dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
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, max (n, m)){
		s[i][0] = s[0][i] = s[n + 1][i] = s[i][m + 1] = '.';
	}
	forn (i, 1, n){
		cin >> t;
		forn (j, 1, m){
			s[i][j] = t[j - 1];
		}
	}
	q.push_back ({1, 1});
	d[1][1] = 1;
	while (sz(q)){
//		for (pii p: q) cout << p.F << " " << p.S << "  ";
//		cout << endl;
		v = q[0];
		q.pop_front();
		forn (i, 0, 3){
			x = v.F + dx[i];
			y = v.S + dy[i];
			if (s[x][y] != '.' && !d[x][y]){
				if (s[x][y] == s[v.F][v.S]){
					d[x][y] = d[v.F][v.S];
					q.push_front ({x, y});
				}
				else{
					d[x][y] = d[v.F][v.S] + 1;
					q.push_back ({x, y});
					ans = max (ans, d[x][y]);
				}
			}
		}
	}
//	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
*/
# Verdict Execution time Memory Grader output
1 Correct 12 ms 6228 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 736 KB Output is correct
4 Correct 8 ms 5716 KB Output is correct
5 Correct 3 ms 3232 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 732 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 3 ms 2260 KB Output is correct
12 Correct 7 ms 3412 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 5 ms 3160 KB Output is correct
15 Correct 10 ms 5888 KB Output is correct
16 Correct 11 ms 6228 KB Output is correct
17 Correct 9 ms 5992 KB Output is correct
18 Correct 9 ms 5716 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 18 ms 31024 KB Output is correct
2 Correct 40 ms 16776 KB Output is correct
3 Correct 198 ms 75760 KB Output is correct
4 Correct 78 ms 43348 KB Output is correct
5 Correct 168 ms 62424 KB Output is correct
6 Correct 728 ms 170524 KB Output is correct
7 Correct 20 ms 32468 KB Output is correct
8 Correct 20 ms 31084 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 6 ms 16084 KB Output is correct
11 Correct 17 ms 31828 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 50 ms 16776 KB Output is correct
14 Correct 27 ms 11728 KB Output is correct
15 Correct 29 ms 16016 KB Output is correct
16 Correct 26 ms 11348 KB Output is correct
17 Correct 96 ms 32320 KB Output is correct
18 Correct 93 ms 47468 KB Output is correct
19 Correct 77 ms 43256 KB Output is correct
20 Correct 52 ms 27724 KB Output is correct
21 Correct 117 ms 53936 KB Output is correct
22 Correct 155 ms 62420 KB Output is correct
23 Correct 172 ms 52316 KB Output is correct
24 Correct 120 ms 52756 KB Output is correct
25 Correct 497 ms 141664 KB Output is correct
26 Incorrect 568 ms 186124 KB Output isn't correct
27 Correct 656 ms 175556 KB Output is correct
28 Correct 636 ms 170512 KB Output is correct
29 Correct 754 ms 168224 KB Output is correct
30 Correct 787 ms 171676 KB Output is correct
31 Correct 621 ms 106404 KB Output is correct
32 Correct 719 ms 167224 KB Output is correct