oj.uz

Submission #989584

# Submission time Handle Problem Language Result Execution time Memory
989584 2024-05-28T11:00:56 Z Nurislam Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 594 ms 256600 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];
		}
	}
	deque<pair<int, pii> > q;
	q.pb({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.front();
		auto [x, y] = ps;
		q.pop_front();
		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;
			if(a[nx][ny] == a[x][y])q.push_front({dis, {nx, ny}});
			else q.pb({dis+1,{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 11 ms 2648 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 2396 KB Output is correct
5 Correct 2 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 8 ms 2732 KB Output is correct
16 Correct 9 ms 2652 KB Output is correct
17 Correct 7 ms 2492 KB Output is correct
18 Correct 5 ms 2396 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 36 ms 14244 KB Output is correct
3 Correct 309 ms 141280 KB Output is correct
4 Correct 71 ms 33364 KB Output is correct
5 Correct 188 ms 79444 KB Output is correct
6 Correct 591 ms 180280 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 1028 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 35 ms 14244 KB Output is correct
14 Correct 20 ms 8284 KB Output is correct
15 Correct 18 ms 9108 KB Output is correct
16 Correct 17 ms 5980 KB Output is correct
17 Correct 120 ms 36156 KB Output is correct
18 Correct 76 ms 35652 KB Output is correct
19 Correct 77 ms 33360 KB Output is correct
20 Correct 60 ms 30724 KB Output is correct
21 Correct 157 ms 82256 KB Output is correct
22 Correct 191 ms 79444 KB Output is correct
23 Correct 207 ms 68692 KB Output is correct
24 Correct 153 ms 80468 KB Output is correct
25 Correct 420 ms 141276 KB Output is correct
26 Correct 377 ms 256600 KB Output is correct
27 Correct 443 ms 193084 KB Output is correct
28 Correct 584 ms 179908 KB Output is correct
29 Correct 594 ms 180984 KB Output is correct
30 Correct 567 ms 181508 KB Output is correct
31 Correct 417 ms 91864 KB Output is correct
32 Correct 434 ms 187248 KB Output is correct