oj.uz

Submission #989579

# Submission time Handle Problem Language Result Execution time Memory
989579 2024-05-28T10:50:52 Z Nurislam Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 190780 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, cnt = 0;
	int us[h][w]{};
	us[0][0] = 1;
	while(!q.empty()){
		auto [dis, ps] = q.top();
		auto [x, y] = ps;
		q.pop();
		ans = max(ans, dis);
		//cout << dis << ' ' << ++cnt << '\n';
		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(us[nx][ny])continue;
			us[nx][ny] = 1;
			q.push({dis + (a[x][y] != a[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:43:15: warning: unused variable 'cnt' [-Wunused-variable]
   43 |  int ans = 1, cnt = 0;
      |               ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2844 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 21 ms 2328 KB Output is correct
5 Correct 5 ms 1112 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 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 5 ms 1052 KB Output is correct
11 Correct 6 ms 1052 KB Output is correct
12 Correct 14 ms 1388 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 33 ms 2652 KB Output is correct
16 Correct 35 ms 2840 KB Output is correct
17 Correct 17 ms 2392 KB Output is correct
18 Correct 21 ms 2332 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 101 ms 14172 KB Output is correct
3 Correct 402 ms 141140 KB Output is correct
4 Correct 118 ms 33404 KB Output is correct
5 Correct 198 ms 79444 KB Output is correct
6 Execution timed out 2047 ms 190708 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 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 99 ms 14340 KB Output is correct
14 Correct 56 ms 8448 KB Output is correct
15 Correct 22 ms 9048 KB Output is correct
16 Correct 53 ms 6236 KB Output is correct
17 Correct 261 ms 36300 KB Output is correct
18 Correct 103 ms 35412 KB Output is correct
19 Correct 122 ms 33520 KB Output is correct
20 Correct 106 ms 30544 KB Output is correct
21 Correct 238 ms 82252 KB Output is correct
22 Correct 203 ms 79644 KB Output is correct
23 Correct 530 ms 68880 KB Output is correct
24 Correct 181 ms 80492 KB Output is correct
25 Correct 596 ms 141396 KB Output is correct
26 Correct 975 ms 108488 KB Output is correct
27 Execution timed out 2087 ms 147516 KB Time limit exceeded
28 Execution timed out 2070 ms 190780 KB Time limit exceeded
29 Execution timed out 2037 ms 166048 KB Time limit exceeded
30 Execution timed out 2071 ms 162980 KB Time limit exceeded
31 Correct 1847 ms 92312 KB Output is correct
32 Correct 1910 ms 144392 KB Output is correct