Submission #1053654

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053654	2024-08-11T15:05:06 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	63.2292 / 100	2000 ms	60284 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}});
	vis[0][0]=1;
	int ans=0;
	while(!pq.empty())
	{
		int x=pq.top().se.fi,y=pq.top().se.se,v=-pq.top().fi;
		pq.pop();
		ans=max(ans,v);
		if(x-1>=0 && !vis[x-1][y] && s[x-1][y]!='.')
		{
			vis[x-1][y]=1;
			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]!='.')
		{
			vis[x][y-1]=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]!='.')
		{
			vis[x+1][y]=1;
			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]!='.')
		{
			vis[x][y+1]=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	26 ms	2652 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	25 ms	2960 KB	Output isn't correct
5	Correct	2 ms	1688 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Incorrect	1 ms	604 KB	Output isn't correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	3 ms	1372 KB	Output is correct
11	Correct	4 ms	1372 KB	Output is correct
12	Correct	9 ms	1796 KB	Output is correct
13	Correct	2 ms	1628 KB	Output is correct
14	Correct	3 ms	1624 KB	Output is correct
15	Correct	20 ms	2900 KB	Output is correct
16	Incorrect	26 ms	2652 KB	Output isn't correct
17	Correct	11 ms	2396 KB	Output is correct
18	Incorrect	28 ms	3100 KB	Output isn't correct

Subtask #2

41.5625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1066 ms	28644 KB	Output isn't correct
2	Correct	65 ms	7000 KB	Output is correct
3	Correct	190 ms	33884 KB	Output is correct
4	Incorrect	59 ms	11744 KB	Output isn't correct
5	Correct	71 ms	21848 KB	Output is correct
6	Correct	1962 ms	60284 KB	Output is correct
7	Correct	1287 ms	42496 KB	Output is correct
8	Incorrect	1047 ms	28856 KB	Output isn't correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Incorrect	1082 ms	42000 KB	Output isn't correct
12	Correct	1 ms	860 KB	Output is correct
13	Correct	62 ms	7004 KB	Output is correct
14	Incorrect	38 ms	4800 KB	Output isn't correct
15	Correct	7 ms	5212 KB	Output is correct
16	Incorrect	1 ms	1372 KB	Output isn't correct
17	Correct	169 ms	12776 KB	Output is correct
18	Correct	41 ms	12380 KB	Output is correct
19	Incorrect	61 ms	11860 KB	Output isn't correct
20	Incorrect	5 ms	4188 KB	Output isn't correct
21	Correct	112 ms	22876 KB	Output is correct
22	Correct	76 ms	21852 KB	Output is correct
23	Incorrect	248 ms	16900 KB	Output isn't correct
24	Correct	65 ms	24020 KB	Output is correct
25	Correct	186 ms	33880 KB	Output is correct
26	Correct	962 ms	27736 KB	Output is correct
27	Correct	1634 ms	38240 KB	Output is correct
28	Correct	1937 ms	58792 KB	Output is correct
29	Execution timed out	2017 ms	48268 KB	Time limit exceeded
30	Correct	1919 ms	47284 KB	Output is correct
31	Incorrect	1267 ms	24920 KB	Output isn't correct
32	Correct	1240 ms	35536 KB	Output is correct