oj.uz

답안 #989554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989554 2024-05-28T10:10:08 Z Nurislam Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 190596 KB 
///*                                                    __                    __                        __                    */
///*        ======     _      /| /|  __   _            /   |  |   /|  |   *  |    |  |  | /   /| |\  | /   |  |  * | /        */
///* \-       ||  |_| |_     / |/ | |  | |_  |-        |   |--|  /-|  |   |  \ \  |==|  |-   /=| | \ | |   |--|  | |-         */
///*          ||  | | |_    /     | |__|  _| |_        \__ |  | /  |  |__ |  __|  |  |  | \ /  | |  \| \__ |  |  | | \        */
///* 
// autor :: Rick Prime
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define Mp make_pair
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
const int N = 1e6, inf = 2e18, mod = 1e9+7;

void solve(){
	//freopen("snakes.in", "r", stdin);
	//freopen("snakes.out", "w", stdout );
	int h, w;
	cin >> h >> w;
	char a[h][w];
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> a[i][j];
		}
	}
	priority_queue<pair<int, pii>> q;
	q.push({-1,{0, 0}});
	vi di = {-1, 1, 0, 0};
	vi dj = {0, 0, -1, 1};
	int ans = 1;
	int ds[h][w]{};
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			ds[i][j] = -inf;
		}
	}
	ds[0][0] = -1;
	while(!q.empty()){
		auto [dis, ps] = q.top();
		auto [x, y] = ps;
		q.pop();
		if(ds[x][y] > dis)continue;
		for(int k = 0; k < 4; k++){
			int nx = x + di[k];
			int ny = y + dj[k];
			if(nx<0 || ny<0 || nx>=h || ny>=w || a[nx][ny] == '.')continue;
			if(ds[nx][ny] >= dis - (a[x][y] != a[nx][ny]))continue;
			ds[nx][ny] = dis - (a[x][y] != a[nx][ny]);
			q.push({ds[nx][ny], {nx, ny}});
		}
	}
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++)ans = max(ans, -(ds[i][j]==-inf?inf:ds[i][j]));
		//{
			//if(ds[i][j] == -inf){
				//cout << "?" << ' ';
				//continue;
			//}
			//cout << -ds[i][j] << ' ';
		//}cout << '\n';
	}
	cout << ans << '\n';
}
 
 
 
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int test = 1;
	//cin >> test;
	while(test--){
		solve();
	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2840 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 22 ms 2648 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 6 ms 856 KB Output is correct
11 Correct 6 ms 1052 KB Output is correct
12 Correct 12 ms 1372 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 27 ms 2824 KB Output is correct
16 Correct 36 ms 2844 KB Output is correct
17 Correct 17 ms 2640 KB Output is correct
18 Correct 22 ms 2504 KB Output is correct

Subtask #2
59.0625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 102 ms 14336 KB Output is correct
3 Correct 432 ms 141396 KB Output is correct
4 Correct 138 ms 33360 KB Output is correct
5 Correct 214 ms 79532 KB Output is correct
6 Execution timed out 2040 ms 190596 KB Time limit exceeded
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 1 ms 644 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 102 ms 14272 KB Output is correct
14 Correct 70 ms 8284 KB Output is correct
15 Correct 20 ms 9052 KB Output is correct
16 Correct 50 ms 5980 KB Output is correct
17 Correct 270 ms 36152 KB Output is correct
18 Correct 110 ms 35632 KB Output is correct
19 Correct 128 ms 33368 KB Output is correct
20 Correct 100 ms 30544 KB Output is correct
21 Correct 285 ms 82260 KB Output is correct
22 Correct 239 ms 79440 KB Output is correct
23 Correct 567 ms 68936 KB Output is correct
24 Correct 179 ms 80464 KB Output is correct
25 Correct 589 ms 141276 KB Output is correct
26 Correct 1406 ms 108560 KB Output is correct
27 Execution timed out 2040 ms 147464 KB Time limit exceeded
28 Execution timed out 2041 ms 190472 KB Time limit exceeded
29 Execution timed out 2049 ms 166052 KB Time limit exceeded
30 Execution timed out 2032 ms 162980 KB Time limit exceeded
31 Correct 1840 ms 92256 KB Output is correct
32 Correct 1880 ms 144420 KB Output is correct