Submission #307087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307087	2020-09-27T02:01:15 Z	Rainbowbunny	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1492 ms	89212 KB

tracks

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
const long long INF = 1e15;
const int mod = 998244353;//1e9 + 7;//786433;
const double Pi = acos(-1);
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int h, w;
char g;
char a[4005][4005];
queue <pair <int, int> > BFS, Wait;
int cnt = 0;
bool Vis[4005][4005], Marked[4005][4005];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
signed main()
{
	Fastio();
	cin >> h >> w;
	for(int i = 1; i <= h; i++)
	{
		for(int j = 1; j <= w; j++)
		{
			cin >> a[i][j];
		}
	}
	Wait.push(mp(1, 1));
	while(Wait.empty() == false)
	{
		++cnt;
		g = a[Wait.front().fi][Wait.front().se];
		while(Wait.empty() == false)
		{
			BFS.push(Wait.front());
			Wait.pop();
		}
		while(BFS.empty() == false)
		{
			int x = BFS.front().fi, y = BFS.front().se;
			Vis[x][y] = true;
			BFS.pop();
			for(int i = 0; i < 4; i++)
			{
				int tx = x + dx[i], ty = y + dy[i];
				if(!Vis[tx][ty] && a[tx][ty] == g)
				{
					BFS.push(mp(tx, ty));
					Vis[tx][ty] = true;
				}
				else if(!Vis[tx][ty] && a[tx][ty] != '.' && a[tx][ty] != 0 && !Marked[tx][ty])
				{
					Marked[tx][ty] = true;
					Wait.push(mp(tx, ty));
				}
			}
		}
	}
	cout << cnt;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	6528 KB	Output is correct
2	Correct	1 ms	640 KB	Output is correct
3	Correct	1 ms	896 KB	Output is correct
4	Correct	14 ms	6656 KB	Output is correct
5	Correct	6 ms	3840 KB	Output is correct
6	Correct	1 ms	640 KB	Output is correct
7	Correct	1 ms	896 KB	Output is correct
8	Correct	2 ms	1024 KB	Output is correct
9	Correct	2 ms	1536 KB	Output is correct
10	Correct	5 ms	3328 KB	Output is correct
11	Correct	5 ms	2816 KB	Output is correct
12	Correct	11 ms	3968 KB	Output is correct
13	Correct	6 ms	3840 KB	Output is correct
14	Correct	47 ms	3832 KB	Output is correct
15	Correct	28 ms	6528 KB	Output is correct
16	Correct	27 ms	6528 KB	Output is correct
17	Correct	17 ms	6304 KB	Output is correct
18	Correct	14 ms	6656 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	40056 KB	Output is correct
2	Correct	93 ms	16592 KB	Output is correct
3	Correct	449 ms	62968 KB	Output is correct
4	Correct	126 ms	26232 KB	Output is correct
5	Correct	269 ms	44408 KB	Output is correct
6	Correct	1492 ms	89212 KB	Output is correct
7	Correct	30 ms	41724 KB	Output is correct
8	Correct	29 ms	40056 KB	Output is correct
9	Correct	4 ms	640 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Correct	29 ms	39160 KB	Output is correct
12	Correct	2 ms	2176 KB	Output is correct
13	Correct	90 ms	16632 KB	Output is correct
14	Correct	52 ms	12024 KB	Output is correct
15	Correct	37 ms	13048 KB	Output is correct
16	Correct	39 ms	5752 KB	Output is correct
17	Correct	236 ms	28024 KB	Output is correct
18	Correct	134 ms	27768 KB	Output is correct
19	Correct	126 ms	26232 KB	Output is correct
20	Correct	108 ms	24312 KB	Output is correct
21	Correct	278 ms	45948 KB	Output is correct
22	Correct	271 ms	44536 KB	Output is correct
23	Correct	453 ms	37368 KB	Output is correct
24	Correct	237 ms	43640 KB	Output is correct
25	Correct	558 ms	63184 KB	Output is correct
26	Correct	575 ms	39960 KB	Output is correct
27	Correct	867 ms	69368 KB	Output is correct
28	Correct	1475 ms	89160 KB	Output is correct
29	Correct	1400 ms	83676 KB	Output is correct
30	Correct	1191 ms	80716 KB	Output is correct
31	Correct	1253 ms	49016 KB	Output is correct
32	Correct	776 ms	64888 KB	Output is correct