oj.uz

Submission #26488

# Submission time Handle Problem Language Result Execution time Memory
26488 2017-07-01T10:14:44 Z samir_droubi Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 1216 ms 1048576 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;
void dfs(int x,int y)
{
	++c;
	g[x][y]='.';
	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;
		}
		dfs(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];
			dfs(x,y);
		}
		v=vv;
		vv.clear();
		++ans;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:38: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:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();++i)
                ^
tracks.cpp:36: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:38: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 16 ms 18936 KB Output is correct
2 Correct 0 ms 17684 KB Output is correct
3 Correct 0 ms 17684 KB Output is correct
4 Correct 6 ms 23156 KB Output is correct
5 Correct 0 ms 17824 KB Output is correct
6 Correct 0 ms 17684 KB Output is correct
7 Correct 0 ms 17684 KB Output is correct
8 Correct 0 ms 17824 KB Output is correct
9 Correct 0 ms 17684 KB Output is correct
10 Correct 0 ms 17824 KB Output is correct
11 Correct 3 ms 18892 KB Output is correct
12 Correct 3 ms 18248 KB Output is correct
13 Correct 0 ms 17824 KB Output is correct
14 Correct 0 ms 17824 KB Output is correct
15 Correct 13 ms 18400 KB Output is correct
16 Correct 9 ms 18936 KB Output is correct
17 Correct 3 ms 17956 KB Output is correct
18 Correct 6 ms 23152 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17884 KB Output is correct
2 Correct 43 ms 17960 KB Output is correct
3 Correct 273 ms 18420 KB Output is correct
4 Correct 49 ms 18020 KB Output is correct
5 Correct 319 ms 18116 KB Output is correct
6 Correct 1116 ms 538296 KB Output is correct
7 Correct 3 ms 17888 KB Output is correct
8 Correct 3 ms 17880 KB Output is correct
9 Correct 0 ms 18228 KB Output is correct
10 Correct 0 ms 17884 KB Output is correct
11 Correct 0 ms 17884 KB Output is correct
12 Correct 0 ms 17684 KB Output is correct
13 Correct 46 ms 17956 KB Output is correct
14 Correct 19 ms 17956 KB Output is correct
15 Correct 23 ms 17824 KB Output is correct
16 Correct 23 ms 17956 KB Output is correct
17 Correct 123 ms 18264 KB Output is correct
18 Correct 93 ms 17892 KB Output is correct
19 Correct 63 ms 18020 KB Output is correct
20 Correct 66 ms 17876 KB Output is correct
21 Correct 163 ms 18116 KB Output is correct
22 Correct 293 ms 18108 KB Output is correct
23 Correct 259 ms 18412 KB Output is correct
24 Correct 199 ms 18112 KB Output is correct
25 Correct 423 ms 18204 KB Output is correct
26 Memory limit exceeded 1216 ms 1048576 KB Memory limit exceeded
27 Correct 1056 ms 664200 KB Output is correct
28 Correct 1123 ms 538304 KB Output is correct
29 Correct 1153 ms 523044 KB Output is correct
30 Correct 1199 ms 664036 KB Output is correct
31 Correct 863 ms 27016 KB Output is correct
32 Correct 1012 ms 986852 KB Output is correct