oj.uz

Submission #989578

# Submission time Handle Problem Language Result Execution time Memory
989578 2024-05-28T10:50:07 Z Nurislam Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 251540 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();
	}
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 5028 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 41 ms 3588 KB Output isn't correct
5 Incorrect 6 ms 1388 KB Output isn't correct
6 Incorrect 0 ms 460 KB Output isn't correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Incorrect 7 ms 1116 KB Output isn't correct
11 Incorrect 10 ms 1264 KB Output isn't correct
12 Incorrect 20 ms 2140 KB Output isn't correct
13 Incorrect 5 ms 1372 KB Output isn't correct
14 Incorrect 5 ms 1240 KB Output isn't correct
15 Incorrect 54 ms 4580 KB Output isn't correct
16 Incorrect 61 ms 5072 KB Output isn't correct
17 Incorrect 27 ms 3664 KB Output isn't correct
18 Incorrect 44 ms 3664 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 856 KB Output isn't correct
2 Incorrect 182 ms 22556 KB Output isn't correct
3 Incorrect 795 ms 212700 KB Output isn't correct
4 Incorrect 191 ms 43136 KB Output isn't correct
5 Incorrect 704 ms 158548 KB Output isn't correct
6 Execution timed out 2088 ms 251164 KB Time limit exceeded
7 Incorrect 3 ms 860 KB Output isn't correct
8 Incorrect 3 ms 860 KB Output isn't correct
9 Incorrect 7 ms 1288 KB Output isn't correct
10 Incorrect 2 ms 832 KB Output isn't correct
11 Incorrect 2 ms 888 KB Output isn't correct
12 Incorrect 2 ms 600 KB Output isn't correct
13 Incorrect 157 ms 22492 KB Output isn't correct
14 Incorrect 114 ms 13140 KB Output isn't correct
15 Incorrect 46 ms 13652 KB Output isn't correct
16 Incorrect 85 ms 10404 KB Output isn't correct
17 Incorrect 418 ms 58448 KB Output isn't correct
18 Incorrect 209 ms 54880 KB Output isn't correct
19 Incorrect 180 ms 43216 KB Output isn't correct
20 Incorrect 180 ms 45652 KB Output isn't correct
21 Incorrect 505 ms 123956 KB Output isn't correct
22 Incorrect 725 ms 158432 KB Output isn't correct
23 Incorrect 936 ms 114036 KB Output isn't correct
24 Incorrect 459 ms 134228 KB Output isn't correct
25 Incorrect 1110 ms 226780 KB Output isn't correct
26 Execution timed out 2066 ms 230980 KB Time limit exceeded
27 Execution timed out 2040 ms 238312 KB Time limit exceeded
28 Execution timed out 2008 ms 245576 KB Time limit exceeded
29 Execution timed out 2062 ms 251540 KB Time limit exceeded
30 Execution timed out 2029 ms 240008 KB Time limit exceeded
31 Execution timed out 2035 ms 174320 KB Time limit exceeded
32 Execution timed out 2037 ms 241948 KB Time limit exceeded