oj.uz

Submission #134003

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

#define MAXN 4005
#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] , id[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);
		}

	memset(marc,false,sizeof marc) ;
	
	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:56: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 55 ms 23436 KB Output is correct
2 Correct 15 ms 16120 KB Output is correct
3 Correct 15 ms 16248 KB Output is correct
4 Correct 33 ms 20596 KB Output is correct
5 Correct 22 ms 17784 KB Output is correct
6 Correct 15 ms 16120 KB Output is correct
7 Correct 15 ms 16248 KB Output is correct
8 Correct 16 ms 16376 KB Output is correct
9 Correct 19 ms 16504 KB Output is correct
10 Correct 22 ms 17784 KB Output is correct
11 Correct 20 ms 17784 KB Output is correct
12 Correct 30 ms 18672 KB Output is correct
13 Correct 26 ms 17784 KB Output is correct
14 Correct 23 ms 17912 KB Output is correct
15 Correct 47 ms 21352 KB Output is correct
16 Correct 54 ms 23268 KB Output is correct
17 Correct 41 ms 20048 KB Output is correct
18 Correct 33 ms 20596 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31864 KB Output is correct
2 Correct 166 ms 35676 KB Output is correct
3 Correct 1159 ms 112504 KB Output is correct
4 Correct 296 ms 42724 KB Output is correct
5 Correct 762 ms 129484 KB Output is correct
6 Correct 1965 ms 194916 KB Output is correct
7 Correct 38 ms 32632 KB Output is correct
8 Correct 36 ms 31992 KB Output is correct
9 Correct 21 ms 17016 KB Output is correct
10 Correct 17 ms 16504 KB Output is correct
11 Correct 30 ms 32248 KB Output is correct
12 Correct 17 ms 17016 KB Output is correct
13 Correct 168 ms 35604 KB Output is correct
14 Correct 102 ms 27620 KB Output is correct
15 Correct 94 ms 26216 KB Output is correct
16 Correct 84 ms 24548 KB Output is correct
17 Correct 403 ms 57040 KB Output is correct
18 Correct 351 ms 48348 KB Output is correct
19 Correct 294 ms 42724 KB Output is correct
20 Correct 272 ms 45248 KB Output is correct
21 Correct 688 ms 81784 KB Output is correct
22 Correct 746 ms 129176 KB Output is correct
23 Correct 764 ms 88532 KB Output is correct
24 Correct 655 ms 81128 KB Output is correct
25 Correct 1390 ms 112328 KB Output is correct
26 Execution timed out 2149 ms 838008 KB Time limit exceeded
27 Correct 1927 ms 490600 KB Output is correct
28 Correct 1869 ms 194920 KB Output is correct
29 Correct 1821 ms 189576 KB Output is correct
30 Correct 1889 ms 273120 KB Output is correct
31 Correct 1635 ms 198724 KB Output is correct
32 Execution timed out 2075 ms 435620 KB Time limit exceeded