oj.uz

Submission #26489

# Submission time Handle Problem Language Result Execution time Memory
26489 2017-07-01T10:21:41 Z samir_droubi Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1416 ms 838424 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxn=4005;
char g[mxn][mxn];
int n,m;
 
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool check(int x,int y)
{
	return x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='*';
}
char ty;
int c=0;
vector<pair<int,int> >v;
vector<pair<int,int> >vv;
queue<pair<int,int> >q;
void bfs()
{
	while(!q.empty())
	{
		int x=q.front().first;
		int y=q.front().second;
		++c;
		q.pop();
		for(int i=0;i<4;++i)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(!check(xx,yy))continue;
			if(g[xx][yy]!=ty)
			{
				vv.push_back({xx,yy});
				continue;
			}
			q.push({xx,yy});
			g[xx][yy]='.';
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int cnt=n*m;
	for(int i=0;i<n;++i)scanf("%s",&g[i]);
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
			if(g[i][j]=='.')
				--cnt;
	}
	v.push_back({0,0});
	int ans=0;
	while(c!=cnt)
	{
		for(int i=0;i<v.size();++i)
		{
			int x=v[i].first;
			int y=v[i].second;
			if(g[x][y]=='.')continue;
			ty=g[x][y];
			g[x][y]='.';
			q.push({x,y});
			bfs();
		}
		v=vv;
		vv.clear();
		++ans;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:45:38: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[4005]' [-Wformat=]
  for(int i=0;i<n;++i)scanf("%s",&g[i]);
                                      ^
tracks.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();++i)
                ^
tracks.cpp:43:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
tracks.cpp:45:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;++i)scanf("%s",&g[i]);
                                       ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18940 KB Output is correct
2 Correct 0 ms 17688 KB Output is correct
3 Correct 0 ms 17688 KB Output is correct
4 Correct 13 ms 22760 KB Output is correct
5 Correct 3 ms 17828 KB Output is correct
6 Correct 0 ms 17688 KB Output is correct
7 Correct 0 ms 17688 KB Output is correct
8 Correct 0 ms 17828 KB Output is correct
9 Correct 0 ms 17688 KB Output is correct
10 Correct 3 ms 17828 KB Output is correct
11 Correct 3 ms 18740 KB Output is correct
12 Correct 6 ms 18252 KB Output is correct
13 Correct 0 ms 17828 KB Output is correct
14 Correct 0 ms 17828 KB Output is correct
15 Correct 13 ms 18404 KB Output is correct
16 Correct 16 ms 18940 KB Output is correct
17 Correct 9 ms 17960 KB Output is correct
18 Correct 13 ms 22760 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17828 KB Output is correct
2 Correct 59 ms 17960 KB Output is correct
3 Correct 316 ms 18172 KB Output is correct
4 Correct 66 ms 17960 KB Output is correct
5 Correct 373 ms 17960 KB Output is correct
6 Correct 1316 ms 517496 KB Output is correct
7 Correct 6 ms 17828 KB Output is correct
8 Correct 3 ms 17828 KB Output is correct
9 Correct 3 ms 18172 KB Output is correct
10 Correct 0 ms 17828 KB Output is correct
11 Correct 0 ms 17828 KB Output is correct
12 Correct 0 ms 17688 KB Output is correct
13 Correct 53 ms 17960 KB Output is correct
14 Correct 29 ms 17960 KB Output is correct
15 Correct 33 ms 17828 KB Output is correct
16 Correct 29 ms 17960 KB Output is correct
17 Correct 146 ms 18192 KB Output is correct
18 Correct 109 ms 17828 KB Output is correct
19 Correct 63 ms 17960 KB Output is correct
20 Correct 79 ms 17828 KB Output is correct
21 Correct 193 ms 17960 KB Output is correct
22 Correct 403 ms 17960 KB Output is correct
23 Correct 249 ms 18260 KB Output is correct
24 Correct 236 ms 17960 KB Output is correct
25 Correct 566 ms 18028 KB Output is correct
26 Correct 979 ms 829060 KB Output is correct
27 Correct 1416 ms 532460 KB Output is correct
28 Correct 1293 ms 517496 KB Output is correct
29 Correct 1273 ms 506660 KB Output is correct
30 Correct 1243 ms 598296 KB Output is correct
31 Correct 693 ms 26728 KB Output is correct
32 Correct 1153 ms 838424 KB Output is correct