Submission #961996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
961996	2024-04-13T02:21:25 Z	pcc	Tracks in the Snow (BOI13_tracks)	C++17	60.625 / 100	2000 ms	102212 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>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

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] = 1;
	dq.push_back(tiii(1,1,1));
	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[nr][nc] == '.')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

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1589 ms	66384 KB	Output is correct
2	Correct	9 ms	64348 KB	Output is correct
3	Correct	9 ms	64348 KB	Output is correct
4	Correct	311 ms	65312 KB	Output is correct
5	Correct	76 ms	64680 KB	Output is correct
6	Correct	10 ms	64344 KB	Output is correct
7	Correct	9 ms	64348 KB	Output is correct
8	Correct	11 ms	64344 KB	Output is correct
9	Correct	9 ms	64348 KB	Output is correct
10	Correct	58 ms	64848 KB	Output is correct
11	Correct	45 ms	64600 KB	Output is correct
12	Correct	325 ms	65108 KB	Output is correct
13	Correct	75 ms	64676 KB	Output is correct
14	Correct	70 ms	64676 KB	Output is correct
15	Correct	1206 ms	65720 KB	Output is correct
16	Correct	1588 ms	66468 KB	Output is correct
17	Correct	666 ms	65316 KB	Output is correct
18	Correct	304 ms	65104 KB	Output is correct

Subtask #2

30.625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	64348 KB	Output is correct
2	Execution timed out	2057 ms	68340 KB	Time limit exceeded
3	Execution timed out	2013 ms	96124 KB	Time limit exceeded
4	Execution timed out	2063 ms	73528 KB	Time limit exceeded
5	Correct	75 ms	82152 KB	Output is correct
6	Execution timed out	2062 ms	101904 KB	Time limit exceeded
7	Correct	10 ms	64348 KB	Output is correct
8	Correct	9 ms	64348 KB	Output is correct
9	Correct	483 ms	64668 KB	Output is correct
10	Correct	9 ms	64348 KB	Output is correct
11	Correct	10 ms	64344 KB	Output is correct
12	Correct	9 ms	64348 KB	Output is correct
13	Execution timed out	2064 ms	68300 KB	Time limit exceeded
14	Execution timed out	2051 ms	66824 KB	Time limit exceeded
15	Correct	23 ms	66472 KB	Output is correct
16	Execution timed out	2061 ms	66648 KB	Time limit exceeded
17	Execution timed out	2067 ms	73740 KB	Time limit exceeded
18	Correct	54 ms	72280 KB	Output is correct
19	Execution timed out	2064 ms	73164 KB	Time limit exceeded
20	Execution timed out	2029 ms	71520 KB	Time limit exceeded
21	Execution timed out	2028 ms	83024 KB	Time limit exceeded
22	Correct	73 ms	82152 KB	Output is correct
23	Execution timed out	2035 ms	81548 KB	Time limit exceeded
24	Correct	78 ms	82256 KB	Output is correct
25	Correct	307 ms	96076 KB	Output is correct
26	Correct	450 ms	88544 KB	Output is correct
27	Execution timed out	2062 ms	99136 KB	Time limit exceeded
28	Execution timed out	2041 ms	101756 KB	Time limit exceeded
29	Execution timed out	2051 ms	100496 KB	Time limit exceeded
30	Execution timed out	2033 ms	100224 KB	Time limit exceeded
31	Execution timed out	2007 ms	97048 KB	Time limit exceeded
32	Execution timed out	2073 ms	102212 KB	Time limit exceeded