Submission #961994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
961994	2024-04-13T02:18:06 Z	pcc	Tracks in the Snow (BOI13_tracks)	C++17	51.7708 / 100	2000 ms	117940 KB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>


const int mxn = 4040;
int N,M;
string arr[mxn];
int dist[mxn][mxn];
deque<tiii> dq;
pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dist,-1,sizeof(dist));
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		arr[i] = "."+arr[i]+".";
	}
	arr[0] = arr[N+1] = string(M+2,'.');
	dist[1][1] = 0;
	dq.push_back(tiii(1,1,0));
	while(!dq.empty()){
		auto [r,c,d] = dq.front();
		dq.pop_front();
		if(dist[r][c] != d)continue;
		for(auto &dd:dir){
			int nr = r+dd.fs,nc = c+dd.sc;
			if(arr[r][c] == '.')continue;
			int nd = d+(arr[nr][nc] != arr[r][c]);
			if(dist[nr][nc] == -1||dist[nr][nc]>nd){
				dist[nr][nc] = nd;
				if(nd == d)dq.push_back(tiii(nr,nc,dist[nr][nc]));
				else dq.push_front(tiii(nr,nc,dist[nr][nc]));
			}
		}
	}
	int ans = 0;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)ans = max(ans,dist[i][j]);
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1

23.3333333333 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1468 ms	66704 KB	Output is correct
2	Correct	11 ms	64348 KB	Output is correct
3	Correct	9 ms	64344 KB	Output is correct
4	Incorrect	299 ms	65240 KB	Output isn't correct
5	Correct	81 ms	64764 KB	Output is correct
6	Correct	9 ms	64348 KB	Output is correct
7	Correct	9 ms	64544 KB	Output is correct
8	Incorrect	12 ms	64348 KB	Output isn't correct
9	Correct	10 ms	64284 KB	Output is correct
10	Correct	55 ms	64680 KB	Output is correct
11	Incorrect	55 ms	64604 KB	Output isn't correct
12	Correct	312 ms	65440 KB	Output is correct
13	Correct	78 ms	64764 KB	Output is correct
14	Correct	82 ms	64604 KB	Output is correct
15	Correct	1246 ms	65968 KB	Output is correct
16	Correct	1500 ms	66704 KB	Output is correct
17	Correct	759 ms	65556 KB	Output is correct
18	Incorrect	291 ms	65360 KB	Output isn't correct

Subtask #2

28.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	64348 KB	Output is correct
2	Execution timed out	2043 ms	69948 KB	Time limit exceeded
3	Execution timed out	2039 ms	111564 KB	Time limit exceeded
4	Execution timed out	2024 ms	76708 KB	Time limit exceeded
5	Correct	110 ms	90960 KB	Output is correct
6	Execution timed out	2092 ms	117732 KB	Time limit exceeded
7	Correct	10 ms	64348 KB	Output is correct
8	Correct	10 ms	64368 KB	Output is correct
9	Correct	540 ms	64724 KB	Output is correct
10	Correct	9 ms	64344 KB	Output is correct
11	Correct	11 ms	64344 KB	Output is correct
12	Correct	10 ms	64480 KB	Output is correct
13	Execution timed out	2069 ms	70064 KB	Time limit exceeded
14	Execution timed out	2029 ms	67748 KB	Time limit exceeded
15	Correct	24 ms	67548 KB	Output is correct
16	Execution timed out	2017 ms	67152 KB	Time limit exceeded
17	Execution timed out	2099 ms	77828 KB	Time limit exceeded
18	Correct	71 ms	76116 KB	Output is correct
19	Execution timed out	2040 ms	76648 KB	Time limit exceeded
20	Execution timed out	2039 ms	74812 KB	Time limit exceeded
21	Execution timed out	2021 ms	92144 KB	Time limit exceeded
22	Correct	121 ms	90940 KB	Output is correct
23	Execution timed out	2102 ms	88724 KB	Time limit exceeded
24	Correct	129 ms	91632 KB	Output is correct
25	Correct	336 ms	111444 KB	Output is correct
26	Incorrect	412 ms	100800 KB	Output isn't correct
27	Execution timed out	2068 ms	114888 KB	Time limit exceeded
28	Execution timed out	2069 ms	117672 KB	Time limit exceeded
29	Execution timed out	2094 ms	116204 KB	Time limit exceeded
30	Execution timed out	2099 ms	115428 KB	Time limit exceeded
31	Execution timed out	2007 ms	107540 KB	Time limit exceeded
32	Execution timed out	2074 ms	117940 KB	Time limit exceeded