oj.uz

Submission #134006

# Submission time Handle Problem Language Result Execution time Memory
134006 2019-07-21T22:50:52 Z CaroLinda Tracks in the Snow (BOI13_tracks) C++14
95.625 / 100
 2000 ms 836128 KB 
#include <bits/stdc++.h>

#define MAXN 4002
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back

using namespace std ;

int n , m ;
int mat[MAXN][MAXN] ;
int dx[4] = {1,0,-1,0} ;
int dy[4] = {0,-1,0,1} ;
bool marc[MAXN][MAXN] ;


bool valid(int x, int y)
{ return (x>=0 && x< n && y>=0 && y<m) ; }

vector<pii> v ;

void dfs(int x, int y)
{
	marc[x][y] = true ;
	lp(i,0,4)
	{
		int a = x + dx[i] ;
		int b= y+dy[i] ;
		if( !valid(a,b) || marc[a][b] ) continue ;
		if( mat[a][b] == mat[x][y] ) dfs(a,b) ;
		else if( mat[a][b] == !mat[x][y] ) v.pb(pii(a,b) ) ;
	}
}

int main()
{
	scanf("%d%d", &n , &m ) ;
	lp(i,0,n)
		lp(j,0,m)
		{
			char c ;
			scanf(" %c", &c ) ;
			if(c=='.') mat[i][j] = -1 ;
			else mat[i][j] = (c=='R'?0:1);
		}
	
	int  s = 0 , ini = 0 ;
	v.pb(pii(0,0) ) ;

	int ant = -1 ;

	while( ini < v.size() )
	{
		pii p = v[ini++] ;
		if( mat[p.ff][p.ss] != ant ) { ant = mat[p.ff][p.ss] ; s++ ;}
		dfs(p.ff, p.ss) ;
	}
	printf("%d\n", s ) ;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:54:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while( ini < v.size() )
         ~~~~^~~~~~~~~~
tracks.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n , &m ) ;
  ~~~~~^~~~~~~~~~~~~~~~~~
tracks.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &c ) ;
    ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9444 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 23 ms 6900 KB Output is correct
5 Correct 11 ms 3196 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 1148 KB Output is correct
10 Correct 10 ms 2936 KB Output is correct
11 Correct 8 ms 2680 KB Output is correct
12 Correct 18 ms 4208 KB Output is correct
13 Correct 11 ms 3196 KB Output is correct
14 Correct 11 ms 3192 KB Output is correct
15 Correct 39 ms 7540 KB Output is correct
16 Correct 44 ms 9444 KB Output is correct
17 Correct 31 ms 6252 KB Output is correct
18 Correct 23 ms 6900 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31224 KB Output is correct
2 Correct 165 ms 24932 KB Output is correct
3 Correct 1218 ms 112116 KB Output is correct
4 Correct 302 ms 34404 KB Output is correct
5 Correct 771 ms 125288 KB Output is correct
6 Correct 1918 ms 194900 KB Output is correct
7 Correct 36 ms 32632 KB Output is correct
8 Correct 35 ms 31224 KB Output is correct
9 Correct 8 ms 1400 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 35 ms 31864 KB Output is correct
12 Correct 5 ms 1912 KB Output is correct
13 Correct 165 ms 24924 KB Output is correct
14 Correct 96 ms 15432 KB Output is correct
15 Correct 87 ms 14444 KB Output is correct
16 Correct 75 ms 10340 KB Output is correct
17 Correct 416 ms 48984 KB Output is correct
18 Correct 333 ms 40508 KB Output is correct
19 Correct 306 ms 34504 KB Output is correct
20 Correct 279 ms 36316 KB Output is correct
21 Correct 736 ms 78032 KB Output is correct
22 Correct 777 ms 125364 KB Output is correct
23 Correct 788 ms 82756 KB Output is correct
24 Correct 679 ms 77528 KB Output is correct
25 Correct 1362 ms 112084 KB Output is correct
26 Execution timed out 2115 ms 836128 KB Time limit exceeded
27 Correct 1974 ms 490596 KB Output is correct
28 Correct 1919 ms 194968 KB Output is correct
29 Correct 1879 ms 189444 KB Output is correct
30 Correct 1915 ms 272512 KB Output is correct
31 Correct 1693 ms 195068 KB Output is correct
32 Execution timed out 2088 ms 433604 KB Time limit exceeded