Submission #48447

# Submission time Handle Problem Language Result Execution time Memory
48447 2018-05-13T16:09:24 Z Pajaraja Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
1827 ms 807624 KB
#include <bits/stdc++.h>
using namespace std;
int t[4007][4007],vi[4007][4007],n,m;
queue<pair<int,int> > q[3];
void dfs(int x,int y,int k)
{
	if(x<0 || y<0 || x>=n || y>=m || vi[x][y]) return;
	if(t[x][y]!=k)
	{
		if(t[x][y]==3-k) q[3-k].push(make_pair(x,y));
		return;
	}
	vi[x][y]=true;
	dfs(x-1,y,k);
	dfs(x+1,y,k);
	dfs(x,y-1,k);
	dfs(x,y+1,k);
}
int main()
{
	int sol=0;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		for(int j=0;j<m;j++) t[i][j]=(s[j]=='F'?2:(s[j]=='R'?1:0));
	}
	q[t[0][0]].push(make_pair(0,0));
	for(int i=0;i<5000;i++)
	{
		if(!q[1].empty())
		{
			sol++;
			while(!q[1].empty())
			{
				if(!vi[q[1].front().first][q[1].front().second]) dfs(q[1].front().first,q[1].front().second,1);
				q[1].pop();
			}
		}
		if(!q[2].empty())
		{
			sol++;
			while(!q[2].empty())
			{
				if(!vi[q[2].front().first][q[2].front().second]) dfs(q[2].front().first,q[2].front().second,2);
				q[2].pop();
			}
		}
	}
	printf("%d",sol);
}
# Verdict Execution time Memory Grader output
1 Correct 31 ms 6520 KB Output is correct
2 Correct 2 ms 6520 KB Output is correct
3 Correct 2 ms 6520 KB Output is correct
4 Correct 20 ms 6924 KB Output is correct
5 Correct 10 ms 6924 KB Output is correct
6 Correct 2 ms 6924 KB Output is correct
7 Correct 2 ms 6924 KB Output is correct
8 Correct 3 ms 6924 KB Output is correct
9 Correct 3 ms 6924 KB Output is correct
10 Correct 8 ms 6924 KB Output is correct
11 Correct 6 ms 6924 KB Output is correct
12 Correct 13 ms 6924 KB Output is correct
13 Correct 9 ms 6924 KB Output is correct
14 Correct 9 ms 6924 KB Output is correct
15 Correct 28 ms 7664 KB Output is correct
16 Correct 31 ms 8056 KB Output is correct
17 Correct 23 ms 8056 KB Output is correct
18 Correct 17 ms 8528 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 31 ms 33768 KB Output is correct
2 Correct 122 ms 33768 KB Output is correct
3 Incorrect 629 ms 99340 KB Output isn't correct
4 Correct 239 ms 99340 KB Output is correct
5 Incorrect 347 ms 99340 KB Output isn't correct
6 Correct 1511 ms 226116 KB Output is correct
7 Correct 32 ms 226116 KB Output is correct
8 Correct 31 ms 226116 KB Output is correct
9 Correct 6 ms 226116 KB Output is correct
10 Correct 3 ms 226116 KB Output is correct
11 Correct 31 ms 226116 KB Output is correct
12 Incorrect 4 ms 226116 KB Output isn't correct
13 Correct 122 ms 226116 KB Output is correct
14 Correct 71 ms 226116 KB Output is correct
15 Incorrect 49 ms 226116 KB Output isn't correct
16 Correct 56 ms 226116 KB Output is correct
17 Correct 310 ms 226116 KB Output is correct
18 Incorrect 177 ms 226116 KB Output isn't correct
19 Correct 228 ms 226116 KB Output is correct
20 Incorrect 149 ms 226116 KB Output isn't correct
21 Incorrect 371 ms 226116 KB Output isn't correct
22 Incorrect 345 ms 226116 KB Output isn't correct
23 Correct 589 ms 226116 KB Output is correct
24 Incorrect 368 ms 226116 KB Output isn't correct
25 Incorrect 652 ms 226116 KB Output isn't correct
26 Correct 1827 ms 807624 KB Output is correct
27 Correct 1498 ms 807624 KB Output is correct
28 Correct 1511 ms 807624 KB Output is correct
29 Correct 1535 ms 807624 KB Output is correct
30 Correct 1511 ms 807624 KB Output is correct
31 Correct 1182 ms 807624 KB Output is correct
32 Correct 1650 ms 807624 KB Output is correct