Submission #1053653

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053653	2024-08-11T15:03:28 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	50.1042 / 100	2000 ms	60332 KB

tracks

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

bool vis[4010][4010];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,m;cin>>n>>m;
	string s[n];
	for(int i=0;i<n;i++) cin>>s[i];

	priority_queue<pair<int,pii>> pq;
	pq.push({0,{0,0}});
	int ans=0;
	while(!pq.empty())
	{
		int x=pq.top().se.fi,y=pq.top().se.se,v=-pq.top().fi;
		pq.pop();
		if(vis[x][y]) continue;
		ans=max(ans,v);
		vis[x][y]=1;
		if(x-1>=0 && !vis[x-1][y] && s[x-1][y]!='.') pq.push({-(v+(s[x][y]!=s[x-1][y])),{x-1,y}});
		if(y-1>=0 && !vis[x][y-1] && s[x][y-1]!='.') pq.push({-(v+(s[x][y]!=s[x][y-1])),{x,y-1}});
		if(x+1<n && !vis[x+1][y] && s[x+1][y]!='.') pq.push({-(v+(s[x][y]!=s[x+1][y])),{x+1,y}});
		if(y+1<n && !vis[x][y+1] && s[x][y+1]!='.') pq.push({-(v+(s[x][y]!=s[x][y+1])),{x,y+1}});
	}
	cout<<ans+1;
	return 0;
}

Subtask #1

21.6666666667 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	52 ms	2908 KB	Output isn't correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Incorrect	47 ms	3484 KB	Output isn't correct
5	Correct	3 ms	1628 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Incorrect	2 ms	604 KB	Output isn't correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	4 ms	1520 KB	Output is correct
11	Correct	7 ms	1372 KB	Output is correct
12	Correct	18 ms	1812 KB	Output is correct
13	Correct	3 ms	1624 KB	Output is correct
14	Correct	3 ms	1628 KB	Output is correct
15	Correct	36 ms	2860 KB	Output is correct
16	Incorrect	52 ms	2904 KB	Output isn't correct
17	Correct	17 ms	2652 KB	Output is correct
18	Incorrect	46 ms	3240 KB	Output isn't correct

Subtask #2

28.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2015 ms	41384 KB	Time limit exceeded
2	Correct	102 ms	7112 KB	Output is correct
3	Correct	264 ms	33884 KB	Output is correct
4	Incorrect	67 ms	11860 KB	Output isn't correct
5	Correct	64 ms	21848 KB	Output is correct
6	Execution timed out	2061 ms	59312 KB	Time limit exceeded
7	Runtime error	109 ms	33360 KB	Execution killed with signal 11
8	Runtime error	98 ms	32076 KB	Execution killed with signal 11
9	Incorrect	0 ms	344 KB	Output isn't correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Execution timed out	2059 ms	41488 KB	Time limit exceeded
12	Correct	1 ms	860 KB	Output is correct
13	Correct	104 ms	7116 KB	Output is correct
14	Incorrect	58 ms	4944 KB	Output isn't correct
15	Correct	6 ms	5208 KB	Output is correct
16	Incorrect	2 ms	1372 KB	Output isn't correct
17	Correct	274 ms	12636 KB	Output is correct
18	Correct	33 ms	12376 KB	Output is correct
19	Incorrect	72 ms	11860 KB	Output isn't correct
20	Incorrect	6 ms	4188 KB	Output isn't correct
21	Correct	169 ms	22876 KB	Output is correct
22	Correct	65 ms	21852 KB	Output is correct
23	Incorrect	403 ms	16980 KB	Output isn't correct
24	Correct	71 ms	24024 KB	Output is correct
25	Correct	182 ms	33884 KB	Output is correct
26	Correct	1449 ms	27736 KB	Output is correct
27	Execution timed out	2081 ms	37104 KB	Time limit exceeded
28	Execution timed out	2063 ms	59108 KB	Time limit exceeded
29	Execution timed out	2100 ms	60332 KB	Time limit exceeded
30	Execution timed out	2074 ms	58552 KB	Time limit exceeded
31	Execution timed out	2045 ms	25808 KB	Time limit exceeded
32	Execution timed out	2061 ms	38400 KB	Time limit exceeded