Submission #1053664

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053664	2024-08-11T15:13:47 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	65.4167 / 100	1933 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}});
	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	1 ms	604 KB	Output is correct
4	Incorrect	28 ms	3040 KB	Output isn't correct
5	Correct	4 ms	1628 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Incorrect	0 ms	604 KB	Output isn't correct
9	Correct	0 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	11 ms	1628 KB	Output is correct
13	Correct	2 ms	1624 KB	Output is correct
14	Correct	2 ms	1628 KB	Output is correct
15	Correct	20 ms	2776 KB	Output is correct
16	Incorrect	27 ms	2648 KB	Output isn't correct
17	Correct	13 ms	2396 KB	Output is correct
18	Incorrect	28 ms	2904 KB	Output isn't correct

Subtask #2

43.75 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1030 ms	29108 KB	Output isn't correct
2	Correct	64 ms	7000 KB	Output is correct
3	Correct	183 ms	33884 KB	Output is correct
4	Incorrect	62 ms	11748 KB	Output isn't correct
5	Correct	69 ms	21852 KB	Output is correct
6	Correct	1933 ms	58904 KB	Output is correct
7	Correct	1292 ms	41392 KB	Output is correct
8	Incorrect	1046 ms	28340 KB	Output isn't correct
9	Incorrect	0 ms	344 KB	Output isn't correct
10	Incorrect	1 ms	344 KB	Output isn't correct
11	Runtime error	51 ms	32760 KB	Execution killed with signal 11
12	Correct	0 ms	860 KB	Output is correct
13	Correct	63 ms	7004 KB	Output is correct
14	Incorrect	35 ms	4948 KB	Output isn't correct
15	Correct	8 ms	5212 KB	Output is correct
16	Incorrect	1 ms	1372 KB	Output isn't correct
17	Correct	168 ms	12780 KB	Output is correct
18	Correct	40 ms	12380 KB	Output is correct
19	Incorrect	67 ms	11740 KB	Output isn't correct
20	Incorrect	5 ms	4188 KB	Output isn't correct
21	Correct	112 ms	22948 KB	Output is correct
22	Correct	74 ms	22032 KB	Output is correct
23	Incorrect	252 ms	16900 KB	Output isn't correct
24	Correct	65 ms	24020 KB	Output is correct
25	Correct	181 ms	33924 KB	Output is correct
26	Correct	989 ms	27848 KB	Output is correct
27	Correct	1582 ms	38400 KB	Output is correct
28	Correct	1926 ms	60332 KB	Output is correct
29	Correct	1923 ms	47348 KB	Output is correct
30	Correct	1879 ms	47544 KB	Output is correct
31	Incorrect	1274 ms	24924 KB	Output isn't correct
32	Correct	1237 ms	35532 KB	Output is correct