oj.uz

Submission #890536

# Submission time Handle Problem Language Result Execution time Memory
890536 2023-12-21T12:15:21 Z thunopro Tracks in the Snow (BOI13_tracks) C++14
89.0625 / 100
 2000 ms 187656 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 4009 
#define ll long long 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1
#define re exit(0);
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1

const int mod = 1e9+7 ; 
const int INF = 1e9 ;
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ;
typedef vector<ll> vl ;  
typedef pair<ll,ll> pll ; 
typedef vector<pll> vll ; 

void add ( int&a , int b ) { if ((a+=b) > mod ) a -= mod ; } 
void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; } 
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

void rf ( ) 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ;
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow ( a , n / 2 ) ; 
	if ( n % 2 ) return ( 1ll * res * res % mod * a % mod ) ; 
	else return ( 1ll * res * res % mod ) ; 
}

int n , m ; 
char a [maxn][maxn] ; 

int dx [] = {0,0,-1,1} ; 
int dy [] = {1,-1,0,0} ;
bool inside ( int x , int y ) 
{
	return (x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!='.') ; 
}
struct shape {
	int u , v , d ; 
	bool operator < ( const shape &o ) const 
	{
		return d > o.d ; 
	}
};
int d [maxn][maxn] ; 
int main ( ) 
{
	ios_base :: sync_with_stdio (0) ; 
	cin.tie(0) ; cout.tie(0) ;
//	rf () ; 
	cin >> n >> m ; 
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) cin >> a [i][j] ; 
	
	priority_queue <shape> S ; 
	memset ( d , 0x3f , sizeof d ) ; 
	d [1][1] = 1 ; 
	S.push ({1,1,d[1][1]}) ; 
	while (!S.empty()) 
	{
		shape t = S.top() ; S.pop() ; 
		int u = t.u , v = t.v ; 
		if ( d [u][v] != t.d ) continue ; 
		for ( int i = 0 ; i < 4 ; i ++ ) 
		{
			int x = u + dx [i] , y = v + dy [i] ; 
			if ( inside (x,y) && d [x][y] > d [u][v] + (a[x][y]!=a[u][v]) ) 
			{
				S . push ({x,y,d[x][y]=d[u][v]+(a[x][y]!=a[u][v])}) ; 
			}
		}
	}
	
	int res = 0 ; 
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) 
	{
		if ( a[i][j] == '.' ) continue ; 
		chkmax (res,d[i][j]) ; 
	}
	cout << res ; 
}




//-std=c++11

Compilation message

tracks.cpp: In function 'void rf()':
tracks.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 66652 KB Output is correct
2 Correct 7 ms 64092 KB Output is correct
3 Correct 8 ms 64168 KB Output is correct
4 Correct 24 ms 66904 KB Output is correct
5 Correct 12 ms 66344 KB Output is correct
6 Correct 7 ms 64092 KB Output is correct
7 Correct 8 ms 64340 KB Output is correct
8 Correct 8 ms 64092 KB Output is correct
9 Correct 8 ms 64092 KB Output is correct
10 Correct 10 ms 66252 KB Output is correct
11 Correct 11 ms 64480 KB Output is correct
12 Correct 16 ms 66396 KB Output is correct
13 Correct 10 ms 66392 KB Output is correct
14 Correct 11 ms 66396 KB Output is correct
15 Correct 26 ms 66636 KB Output is correct
16 Correct 32 ms 66652 KB Output is correct
17 Correct 20 ms 66396 KB Output is correct
18 Correct 24 ms 66944 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 78684 KB Output is correct
2 Correct 80 ms 69436 KB Output is correct
3 Correct 308 ms 87120 KB Output is correct
4 Correct 107 ms 74320 KB Output is correct
5 Correct 177 ms 81104 KB Output is correct
6 Execution timed out 2041 ms 112712 KB Time limit exceeded
7 Correct 10 ms 78940 KB Output is correct
8 Correct 10 ms 78428 KB Output is correct
9 Correct 10 ms 64348 KB Output is correct
10 Correct 8 ms 64092 KB Output is correct
11 Correct 11 ms 78720 KB Output is correct
12 Correct 8 ms 64188 KB Output is correct
13 Correct 86 ms 69440 KB Output is correct
14 Correct 48 ms 68956 KB Output is correct
15 Correct 27 ms 68912 KB Output is correct
16 Correct 43 ms 66648 KB Output is correct
17 Correct 194 ms 74628 KB Output is correct
18 Correct 87 ms 74760 KB Output is correct
19 Correct 105 ms 74404 KB Output is correct
20 Correct 79 ms 72400 KB Output is correct
21 Correct 200 ms 81408 KB Output is correct
22 Correct 176 ms 81140 KB Output is correct
23 Correct 376 ms 78732 KB Output is correct
24 Correct 147 ms 81324 KB Output is correct
25 Correct 397 ms 87228 KB Output is correct
26 Correct 1988 ms 185112 KB Output is correct
27 Execution timed out 2068 ms 113696 KB Time limit exceeded
28 Execution timed out 2021 ms 113748 KB Time limit exceeded
29 Execution timed out 2039 ms 113324 KB Time limit exceeded
30 Execution timed out 2085 ms 137120 KB Time limit exceeded
31 Correct 1205 ms 83412 KB Output is correct
32 Correct 1840 ms 187656 KB Output is correct