oj.uz

Submission #133989

# Submission time Handle Problem Language Result Execution time Memory
133989 2019-07-21T22:13:19 Z CaroLinda Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 1788 ms 260612 KB 
#include <bits/stdc++.h>

#define MAXN 4010
#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 valid(int x, int y)
{ return (x>=0 && x< n && y>=0 && y<m) ; }

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);
		}

	vector<pii> firstGroup , secondGroup ;

	firstGroup.pb( pii(0,0) ) ;
	int ini = 0 ;
	lp(i,0,n)
		lp(j,0,m)
			id[i][j] = MAXN+10 ;
	id[0][0] = 1 ;
	int s = 0 ;

	while( firstGroup.size() != 0 )
	{
		secondGroup.resize(0) ;
		s++ ;
		while( ini < firstGroup.size() )
		{
			pii p = firstGroup[ini++] ;

			for(int i = 0 ; i < 4 ; i++)
			{
				int x = p.ff + dx[i] ;
				int y = p.ss + dy[i] ;
				if( !valid(x,y) || id[x][y] != (MAXN+10) ) continue ;

				if( mat[x][y] == mat[p.ff][p.ss] )
				{
					id[x][y] = id[p.ff][p.ss] ;
					firstGroup.pb( pii(x,y) ) ;
				}
				else if ( mat[x][y] == !mat[p.ff][p.ss] )
				{
					id[x][y] = id[p.ff][p.ss] + 1 ;
					secondGroup.pb( pii(x,y) ) ;
				}
			}

		}

		firstGroup.resize(0) ;

		lp(i,0,secondGroup.size() )
			firstGroup.pb( secondGroup[i] ) ;

	}

	printf("%d\n" , s ) ;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while( ini < firstGroup.size() )
          ~~~~^~~~~~~~~~~~~~~~~~~
tracks.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
tracks.cpp:74:6:
   lp(i,0,secondGroup.size() )
      ~~~~~~~~~~~~~~~~~~~~~~     
tracks.cpp:74:3: note: in expansion of macro 'lp'
   lp(i,0,secondGroup.size() )
   ^~
tracks.cpp:24: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:29:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &c ) ;
    ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 6392 KB Output isn't correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Incorrect 3 ms 760 KB Output isn't correct
4 Incorrect 18 ms 6260 KB Output isn't correct
5 Incorrect 10 ms 3320 KB Output isn't correct
6 Incorrect 2 ms 504 KB Output isn't correct
7 Incorrect 3 ms 760 KB Output isn't correct
8 Incorrect 3 ms 888 KB Output isn't correct
9 Incorrect 4 ms 1144 KB Output isn't correct
10 Incorrect 8 ms 2808 KB Output isn't correct
11 Incorrect 7 ms 2684 KB Output isn't correct
12 Incorrect 10 ms 3448 KB Output isn't correct
13 Incorrect 9 ms 3320 KB Output isn't correct
14 Incorrect 9 ms 3320 KB Output isn't correct
15 Incorrect 22 ms 6380 KB Output isn't correct
16 Incorrect 21 ms 6264 KB Output isn't correct
17 Incorrect 20 ms 6012 KB Output isn't correct
18 Incorrect 19 ms 6260 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 31480 KB Output isn't correct
2 Incorrect 109 ms 22688 KB Output isn't correct
3 Incorrect 1016 ms 126116 KB Output isn't correct
4 Incorrect 259 ms 44884 KB Output isn't correct
5 Incorrect 592 ms 94712 KB Output isn't correct
6 Incorrect 1217 ms 166112 KB Output isn't correct
7 Incorrect 29 ms 32888 KB Output isn't correct
8 Incorrect 34 ms 31480 KB Output isn't correct
9 Incorrect 6 ms 888 KB Output isn't correct
10 Incorrect 4 ms 632 KB Output isn't correct
11 Incorrect 29 ms 32376 KB Output isn't correct
12 Incorrect 4 ms 1784 KB Output isn't correct
13 Incorrect 109 ms 22736 KB Output isn't correct
14 Incorrect 65 ms 14684 KB Output isn't correct
15 Incorrect 75 ms 16248 KB Output isn't correct
16 Incorrect 45 ms 8828 KB Output isn't correct
17 Incorrect 271 ms 48504 KB Output isn't correct
18 Incorrect 284 ms 47728 KB Output isn't correct
19 Incorrect 259 ms 44920 KB Output isn't correct
20 Incorrect 231 ms 41336 KB Output isn't correct
21 Incorrect 618 ms 97784 KB Output isn't correct
22 Incorrect 592 ms 94700 KB Output isn't correct
23 Incorrect 508 ms 79068 KB Output isn't correct
24 Incorrect 599 ms 96660 KB Output isn't correct
25 Incorrect 1120 ms 126280 KB Output isn't correct
26 Correct 1563 ms 241876 KB Output is correct
27 Incorrect 1661 ms 260612 KB Output isn't correct
28 Incorrect 1229 ms 166016 KB Output isn't correct
29 Incorrect 1233 ms 166384 KB Output isn't correct
30 Incorrect 1287 ms 169484 KB Output isn't correct
31 Incorrect 673 ms 101752 KB Output isn't correct
32 Incorrect 1788 ms 257676 KB Output isn't correct