oj.uz

Submission #133988

# Submission time Handle Problem Language Result Execution time Memory
133988 2019-07-21T22:10:16 Z CaroLinda Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 1750 ms 260688 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] <= id[p.ff][p.ss] ) 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:73:6:
   lp(i,0,secondGroup.size() )
      ~~~~~~~~~~~~~~~~~~~~~~     
tracks.cpp:73: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 20 ms 6520 KB Output isn't correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Incorrect 2 ms 760 KB Output isn't correct
4 Incorrect 17 ms 6256 KB Output isn't correct
5 Incorrect 9 ms 3320 KB Output isn't correct
6 Incorrect 2 ms 504 KB Output isn't correct
7 Incorrect 2 ms 760 KB Output isn't correct
8 Incorrect 3 ms 888 KB Output isn't correct
9 Incorrect 3 ms 1272 KB Output isn't correct
10 Incorrect 7 ms 2808 KB Output isn't correct
11 Incorrect 6 ms 2680 KB Output isn't correct
12 Incorrect 9 ms 3448 KB Output isn't correct
13 Incorrect 9 ms 3352 KB Output isn't correct
14 Incorrect 9 ms 3324 KB Output isn't correct
15 Incorrect 20 ms 6520 KB Output isn't correct
16 Incorrect 20 ms 6520 KB Output isn't correct
17 Incorrect 20 ms 6136 KB Output isn't correct
18 Incorrect 16 ms 6256 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 105 ms 22724 KB Output isn't correct
3 Incorrect 941 ms 126140 KB Output isn't correct
4 Incorrect 243 ms 44932 KB Output isn't correct
5 Incorrect 546 ms 94692 KB Output isn't correct
6 Incorrect 1154 ms 167244 KB Output isn't correct
7 Incorrect 30 ms 33016 KB Output isn't correct
8 Incorrect 28 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 1656 KB Output isn't correct
13 Incorrect 101 ms 22672 KB Output isn't correct
14 Incorrect 61 ms 14844 KB Output isn't correct
15 Incorrect 73 ms 16228 KB Output isn't correct
16 Incorrect 42 ms 8668 KB Output isn't correct
17 Incorrect 252 ms 48508 KB Output isn't correct
18 Incorrect 270 ms 47756 KB Output isn't correct
19 Incorrect 241 ms 44848 KB Output isn't correct
20 Incorrect 214 ms 41456 KB Output isn't correct
21 Incorrect 567 ms 97824 KB Output isn't correct
22 Incorrect 545 ms 94592 KB Output isn't correct
23 Incorrect 468 ms 79096 KB Output isn't correct
24 Incorrect 554 ms 96576 KB Output isn't correct
25 Incorrect 1036 ms 126176 KB Output isn't correct
26 Correct 1488 ms 241816 KB Output is correct
27 Incorrect 1588 ms 260688 KB Output isn't correct
28 Incorrect 1148 ms 167292 KB Output isn't correct
29 Incorrect 1161 ms 178480 KB Output isn't correct
30 Incorrect 1174 ms 182752 KB Output isn't correct
31 Incorrect 620 ms 102552 KB Output isn't correct
32 Incorrect 1750 ms 260072 KB Output isn't correct