oj.uz

Submission #134848

# Submission time Handle Problem Language Result Execution time Memory
134848 2019-07-23T10:07:46 Z CaroLinda Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1729 ms 121604 KB 
#include <bits/stdc++.h>

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

const int inf = 0x3f3f3f3f ;
const int MAXN = 4123 ;

using namespace std ;

int n , m ;
int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1} ;
int d[MAXN][MAXN] ;
char mat[MAXN][MAXN] ;
deque<pii> fila ;

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) 
			scanf(" %c", &mat[i][j]) , d[i][j] =inf;

	fila.push_front(mk(0,0)) ;
	d[0][0] = 1 ;
	int ans = 0 ;

	while(!fila.empty())
	{
		pii p = fila.front() ;

		fila.pop_front() ;

		ans=max(ans,d[p.ff][p.ss]) ;

		lp(i,0,4)
		{
			int x = p.ff+dx[i] , y = p.ss+dy[i] ;
			
			if(!valid(x,y) || mat[x][y] =='.' ) continue ;

			if( mat[p.ff][p.ss] == mat[x][y] ){
				if(d[x][y] > d[p.ff][p.ss])
				{
					d[x][y] = d[p.ff][p.ss] ;
					fila.push_front(mk(x,y)); 
				}
			}

			else if(mat[p.ff][p.ss] != mat[x][y])
				if( (d[p.ff][p.ss]+1) < d[x][y] )
				{
					d[x][y] = d[p.ff][p.ss]+1;
					fila.push_back(mk(x,y)) ;
				}
		}
	}

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

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:26: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:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &mat[i][j]) , d[i][j] =inf;
    ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5368 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 20 ms 5240 KB Output is correct
5 Correct 11 ms 3064 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 10 ms 2684 KB Output is correct
11 Correct 8 ms 2168 KB Output is correct
12 Correct 15 ms 3064 KB Output is correct
13 Correct 11 ms 3064 KB Output is correct
14 Correct 10 ms 2984 KB Output is correct
15 Correct 31 ms 5496 KB Output is correct
16 Correct 33 ms 5340 KB Output is correct
17 Correct 27 ms 5240 KB Output is correct
18 Correct 21 ms 5288 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31224 KB Output is correct
2 Correct 151 ms 16828 KB Output is correct
3 Correct 1145 ms 81328 KB Output is correct
4 Correct 289 ms 30492 KB Output is correct
5 Correct 655 ms 60024 KB Output is correct
6 Correct 1727 ms 95392 KB Output is correct
7 Correct 30 ms 32760 KB Output is correct
8 Correct 36 ms 31224 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 30 ms 32120 KB Output is correct
12 Correct 5 ms 1656 KB Output is correct
13 Correct 142 ms 16760 KB Output is correct
14 Correct 83 ms 11512 KB Output is correct
15 Correct 83 ms 12536 KB Output is correct
16 Correct 63 ms 6268 KB Output is correct
17 Correct 360 ms 32888 KB Output is correct
18 Correct 320 ms 32344 KB Output is correct
19 Correct 290 ms 30552 KB Output is correct
20 Correct 259 ms 28280 KB Output is correct
21 Correct 679 ms 61944 KB Output is correct
22 Correct 656 ms 60136 KB Output is correct
23 Correct 680 ms 51036 KB Output is correct
24 Correct 669 ms 61424 KB Output is correct
25 Correct 1334 ms 81400 KB Output is correct
26 Correct 1179 ms 121604 KB Output is correct
27 Correct 1544 ms 116100 KB Output is correct
28 Correct 1727 ms 95528 KB Output is correct
29 Correct 1729 ms 92888 KB Output is correct
30 Correct 1603 ms 98828 KB Output is correct
31 Correct 1260 ms 65508 KB Output is correct
32 Correct 1466 ms 105624 KB Output is correct