oj.uz

Submission #989562

# Submission time Handle Problem Language Result Execution time Memory
989562 2024-05-28T10:14:00 Z Nurislam Tracks in the Snow (BOI13_tracks) C++17
86.875 / 100
 2000 ms 190696 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>, vector<pair<int,pii>>, greater<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;
	int cnt = 0;
	while(!q.empty()){
		auto [dis, ps] = q.top();
		auto [x, y] = ps;
		q.pop();
		if(ds[x][y] > dis)continue;
		ans = max(ans, dis);
		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}});
		}
	}
	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();
	}
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:51:6: warning: unused variable 'cnt' [-Wunused-variable]
   51 |  int cnt = 0;
      |      ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2844 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 21 ms 2316 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 5 ms 1052 KB Output is correct
12 Correct 12 ms 1372 KB Output is correct
13 Correct 3 ms 1212 KB Output is correct
14 Correct 4 ms 1116 KB Output is correct
15 Correct 26 ms 2652 KB Output is correct
16 Correct 36 ms 2840 KB Output is correct
17 Correct 17 ms 2488 KB Output is correct
18 Correct 22 ms 2332 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 103 ms 14260 KB Output is correct
3 Correct 415 ms 141396 KB Output is correct
4 Correct 124 ms 33420 KB Output is correct
5 Correct 202 ms 79440 KB Output is correct
6 Execution timed out 2074 ms 190696 KB Time limit exceeded
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 112 ms 14264 KB Output is correct
14 Correct 55 ms 8284 KB Output is correct
15 Correct 21 ms 9052 KB Output is correct
16 Correct 50 ms 6236 KB Output is correct
17 Correct 271 ms 36180 KB Output is correct
18 Correct 81 ms 35408 KB Output is correct
19 Correct 121 ms 33520 KB Output is correct
20 Correct 115 ms 30544 KB Output is correct
21 Correct 238 ms 82260 KB Output is correct
22 Correct 223 ms 79440 KB Output is correct
23 Correct 527 ms 68788 KB Output is correct
24 Correct 178 ms 80472 KB Output is correct
25 Correct 379 ms 141392 KB Output is correct
26 Correct 948 ms 108488 KB Output is correct
27 Execution timed out 2077 ms 147544 KB Time limit exceeded
28 Execution timed out 2019 ms 190684 KB Time limit exceeded
29 Execution timed out 2052 ms 166052 KB Time limit exceeded
30 Execution timed out 2085 ms 163048 KB Time limit exceeded
31 Correct 1739 ms 92364 KB Output is correct
32 Execution timed out 2048 ms 144452 KB Time limit exceeded