Submission #378205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378205	2021-03-16T08:10:47 Z	penguin133	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1778 ms	332536 KB

tracks

#include <bits/stdc++.h>
using namespace std;
char g[4005][4005];
int ans[4005][4005];
int visited[4005][4005];
int dx[] = {0,1,0,-1}, dy[] = {1, 0, -1, 0};
inline int ReadInt() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
    return x;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int h,w,maxi = 0;
	cin >> h >> w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin >> g[i][j];
		}
	}
	for(int i=1;i<=4000;i++)fill(ans[i] , ans[i] + 4005, 2e9  +5);
	deque<pair<int, int> >q;
	q.push_back(make_pair(1, 1));
	ans[1][1] = 0;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop_front();
		if(visited[x][y] == true)continue;
		visited[x][y] = true;
		for(int i=0;i<4;i++){
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if(x1 < 1 || x1 > h || y1 < 1 ||y1 > w)continue;
			if(g[x1][y1] == '.')continue;
			int ans1 = 0;
			if(g[x1][y1] != g[x][y])ans1++;
			ans[x1][y1] = min(ans[x1][y1], ans[x][y] + ans1);
			if(ans1 == 0)q.push_front(make_pair(x1, y1));
			else q.push_back(make_pair(x1 , y1));
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(g[i][j] == '.')continue;
			maxi = max(maxi, ans[i][j]);
		}
	}
	cout << maxi + 1;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	68076 KB	Output is correct
2	Correct	44 ms	63260 KB	Output is correct
3	Correct	50 ms	63468 KB	Output is correct
4	Correct	57 ms	68076 KB	Output is correct
5	Correct	47 ms	65644 KB	Output is correct
6	Correct	41 ms	63212 KB	Output is correct
7	Correct	43 ms	63616 KB	Output is correct
8	Correct	43 ms	63596 KB	Output is correct
9	Correct	51 ms	63852 KB	Output is correct
10	Correct	49 ms	65132 KB	Output is correct
11	Correct	45 ms	65004 KB	Output is correct
12	Correct	51 ms	65772 KB	Output is correct
13	Correct	46 ms	65644 KB	Output is correct
14	Correct	56 ms	65644 KB	Output is correct
15	Correct	64 ms	67820 KB	Output is correct
16	Correct	69 ms	68076 KB	Output is correct
17	Correct	60 ms	67948 KB	Output is correct
18	Correct	57 ms	68076 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	93548 KB	Output is correct
2	Correct	132 ms	76500 KB	Output is correct
3	Correct	543 ms	120532 KB	Output is correct
4	Correct	193 ms	91884 KB	Output is correct
5	Correct	380 ms	107432 KB	Output is correct
6	Correct	1740 ms	176128 KB	Output is correct
7	Correct	62 ms	94956 KB	Output is correct
8	Correct	61 ms	93548 KB	Output is correct
9	Correct	44 ms	63340 KB	Output is correct
10	Correct	42 ms	63212 KB	Output is correct
11	Correct	62 ms	94316 KB	Output is correct
12	Correct	44 ms	64364 KB	Output is correct
13	Correct	132 ms	76268 KB	Output is correct
14	Correct	97 ms	72300 KB	Output is correct
15	Correct	88 ms	74888 KB	Output is correct
16	Correct	82 ms	67908 KB	Output is correct
17	Correct	265 ms	87668 KB	Output is correct
18	Correct	229 ms	94572 KB	Output is correct
19	Correct	190 ms	91884 KB	Output is correct
20	Correct	160 ms	84972 KB	Output is correct
21	Correct	344 ms	106140 KB	Output is correct
22	Correct	383 ms	107372 KB	Output is correct
23	Correct	477 ms	99052 KB	Output is correct
24	Correct	311 ms	103660 KB	Output is correct
25	Correct	939 ms	141512 KB	Output is correct
26	Correct	1777 ms	332536 KB	Output is correct
27	Correct	1652 ms	237256 KB	Output is correct
28	Correct	1778 ms	176120 KB	Output is correct
29	Correct	1674 ms	174896 KB	Output is correct
30	Correct	1690 ms	196552 KB	Output is correct
31	Correct	1336 ms	127676 KB	Output is correct
32	Correct	1698 ms	233540 KB	Output is correct