oj.uz

답안 #989565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989565 2024-05-28T10:16:50 Z Nurislam Tracks in the Snow (BOI13_tracks) C++17
34.5833 / 100
 2000 ms 941712 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 us[h][w]{};
	while(!q.empty()){
		auto [dis, ps] = q.top();
		auto [x, y] = ps;
		q.pop();
		us[x][y] = 1;
		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(us[nx][ny])continue;
			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
8.33333333333 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2058 ms 420028 KB Time limit exceeded
2 Correct 0 ms 344 KB Output is correct
3 Correct 130 ms 6780 KB Output is correct
4 Execution timed out 2028 ms 396004 KB Time limit exceeded
5 Execution timed out 2077 ms 395236 KB Time limit exceeded
6 Correct 0 ms 348 KB Output is correct
7 Correct 130 ms 6752 KB Output is correct
8 Execution timed out 2021 ms 394536 KB Time limit exceeded
9 Correct 13 ms 1052 KB Output is correct
10 Execution timed out 2104 ms 395012 KB Time limit exceeded
11 Execution timed out 2071 ms 394872 KB Time limit exceeded
12 Execution timed out 2082 ms 789160 KB Time limit exceeded
13 Execution timed out 2037 ms 395408 KB Time limit exceeded
14 Execution timed out 2074 ms 395368 KB Time limit exceeded
15 Execution timed out 2051 ms 396808 KB Time limit exceeded
16 Execution timed out 2074 ms 397020 KB Time limit exceeded
17 Execution timed out 2060 ms 396840 KB Time limit exceeded
18 Execution timed out 2024 ms 395820 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Execution timed out 2092 ms 212700 KB Time limit exceeded
3 Execution timed out 2029 ms 350700 KB Time limit exceeded
4 Execution timed out 2028 ms 135160 KB Time limit exceeded
5 Correct 211 ms 86356 KB Output is correct
6 Execution timed out 2110 ms 547680 KB Time limit exceeded
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Execution timed out 2102 ms 395060 KB Time limit exceeded
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 500 KB Output is correct
13 Execution timed out 2101 ms 212608 KB Time limit exceeded
14 Execution timed out 2057 ms 403244 KB Time limit exceeded
15 Correct 20 ms 10064 KB Output is correct
16 Execution timed out 2079 ms 381576 KB Time limit exceeded
17 Execution timed out 2075 ms 433392 KB Time limit exceeded
18 Correct 97 ms 38736 KB Output is correct
19 Execution timed out 2029 ms 135008 KB Time limit exceeded
20 Execution timed out 2021 ms 132432 KB Time limit exceeded
21 Execution timed out 2016 ms 286676 KB Time limit exceeded
22 Correct 209 ms 86356 KB Output is correct
23 Execution timed out 2043 ms 173408 KB Time limit exceeded
24 Correct 176 ms 87336 KB Output is correct
25 Correct 570 ms 153604 KB Output is correct
26 Execution timed out 2021 ms 511396 KB Time limit exceeded
27 Execution timed out 2060 ms 547708 KB Time limit exceeded
28 Execution timed out 2050 ms 547692 KB Time limit exceeded
29 Execution timed out 2043 ms 547520 KB Time limit exceeded
30 Execution timed out 2088 ms 544036 KB Time limit exceeded
31 Execution timed out 2019 ms 538876 KB Time limit exceeded
32 Execution timed out 2126 ms 941712 KB Time limit exceeded