답안 #649074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
649074	2022-10-09T07:15:58 Z	rickbaishuak	Tracks in the Snow (BOI13_tracks)	C++14	97.8125 / 100	787 ms	186124 KB

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, 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
*/

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	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

Subtask #2

67.8125 / 70.0

#	결과	실행 시간	메모리	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