Submission #378204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378204	2021-03-16T08:06:23 Z	penguin133	Tracks in the Snow (BOI13_tracks)	C++14	71.5625 / 100	2000 ms	142380 KB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
char g[4005][4005];
int ans[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;
}
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);
	queue<pair<int, int> >q;
	q.push(make_pair(1, 1));
	ans[1][1] = 0;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(x == h && y == w)continue;
		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 = ans[x][y];
			if(g[x1][y1] != g[x][y])ans1++;
			if(ans[x1][y1] > ans1){
				ans[x1][y1] = ans1;
				q.push(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;
}

Compilation message

tracks.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main(){
      |      ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	267 ms	127980 KB	Output is correct
2	Correct	73 ms	125932 KB	Output is correct
3	Correct	83 ms	125932 KB	Output is correct
4	Correct	116 ms	127736 KB	Output is correct
5	Correct	85 ms	126956 KB	Output is correct
6	Correct	75 ms	125804 KB	Output is correct
7	Correct	80 ms	125932 KB	Output is correct
8	Correct	71 ms	126080 KB	Output is correct
9	Correct	72 ms	126188 KB	Output is correct
10	Correct	80 ms	126700 KB	Output is correct
11	Correct	76 ms	126572 KB	Output is correct
12	Correct	116 ms	127096 KB	Output is correct
13	Correct	84 ms	126828 KB	Output is correct
14	Correct	92 ms	126956 KB	Output is correct
15	Correct	183 ms	127724 KB	Output is correct
16	Correct	265 ms	128236 KB	Output is correct
17	Correct	195 ms	127868 KB	Output is correct
18	Correct	102 ms	127852 KB	Output is correct

Subtask #2

41.5625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	140780 KB	Output is correct
2	Correct	600 ms	130924 KB	Output is correct
3	Execution timed out	2101 ms	141548 KB	Time limit exceeded
4	Execution timed out	2091 ms	133484 KB	Time limit exceeded
5	Correct	306 ms	137580 KB	Output is correct
6	Execution timed out	2072 ms	142364 KB	Time limit exceeded
7	Correct	90 ms	141420 KB	Output is correct
8	Correct	81 ms	140652 KB	Output is correct
9	Correct	87 ms	125932 KB	Output is correct
10	Correct	73 ms	125780 KB	Output is correct
11	Correct	81 ms	141164 KB	Output is correct
12	Correct	81 ms	126316 KB	Output is correct
13	Correct	605 ms	130816 KB	Output is correct
14	Correct	332 ms	129516 KB	Output is correct
15	Correct	106 ms	129644 KB	Output is correct
16	Correct	566 ms	127596 KB	Output is correct
17	Execution timed out	2065 ms	133996 KB	Time limit exceeded
18	Correct	214 ms	133612 KB	Output is correct
19	Execution timed out	2080 ms	133756 KB	Time limit exceeded
20	Execution timed out	2041 ms	132972 KB	Time limit exceeded
21	Execution timed out	2040 ms	137964 KB	Time limit exceeded
22	Correct	307 ms	137708 KB	Output is correct
23	Execution timed out	2084 ms	136400 KB	Time limit exceeded
24	Correct	274 ms	137964 KB	Output is correct
25	Correct	809 ms	141668 KB	Output is correct
26	Correct	972 ms	139724 KB	Output is correct
27	Correct	1336 ms	141676 KB	Output is correct
28	Execution timed out	2094 ms	142380 KB	Time limit exceeded
29	Execution timed out	2076 ms	142312 KB	Time limit exceeded
30	Execution timed out	2086 ms	141944 KB	Time limit exceeded
31	Execution timed out	2093 ms	139688 KB	Time limit exceeded
32	Execution timed out	2100 ms	142292 KB	Time limit exceeded