oj.uz

Submission #26483

# Submission time Handle Problem Language Result Execution time Memory
26483 2017-07-01T10:04:00 Z samir_droubi Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 1279 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;
}
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 9 ms 23152 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 3 ms 17824 KB Output is correct
11 Correct 3 ms 18884 KB Output is correct
12 Correct 6 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 9 ms 18400 KB Output is correct
16 Correct 13 ms 18936 KB Output is correct
17 Correct 6 ms 17956 KB Output is correct
18 Correct 9 ms 23152 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17876 KB Output is correct
2 Correct 46 ms 17956 KB Output is correct
3 Correct 289 ms 18420 KB Output is correct
4 Correct 63 ms 18016 KB Output is correct
5 Correct 316 ms 18112 KB Output is correct
6 Correct 1146 ms 538304 KB Output is correct
7 Correct 0 ms 17884 KB Output is correct
8 Correct 0 ms 17880 KB Output is correct
9 Correct 3 ms 18232 KB Output is correct
10 Correct 0 ms 17884 KB Output is correct
11 Correct 3 ms 17884 KB Output is correct
12 Correct 0 ms 17684 KB Output is correct
13 Correct 53 ms 17960 KB Output is correct
14 Correct 26 ms 17956 KB Output is correct
15 Correct 19 ms 17824 KB Output is correct
16 Correct 26 ms 17956 KB Output is correct
17 Correct 119 ms 18264 KB Output is correct
18 Correct 83 ms 17884 KB Output is correct
19 Correct 56 ms 18020 KB Output is correct
20 Correct 66 ms 17876 KB Output is correct
21 Correct 153 ms 18116 KB Output is correct
22 Correct 323 ms 18112 KB Output is correct
23 Correct 249 ms 18416 KB Output is correct
24 Correct 213 ms 18116 KB Output is correct
25 Correct 419 ms 18204 KB Output is correct
26 Memory limit exceeded 1279 ms 1048576 KB Memory limit exceeded
27 Correct 1049 ms 664196 KB Output is correct
28 Correct 1136 ms 538300 KB Output is correct
29 Correct 1073 ms 523052 KB Output is correct
30 Correct 1143 ms 664036 KB Output is correct
31 Correct 746 ms 27020 KB Output is correct
32 Correct 973 ms 986848 KB Output is correct