oj.uz

답안 #910591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910591 2024-01-18T06:07:07 Z oblantis Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 841 ms 1048576 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const int inf = 1e9 + 10000;
const int mod = 1e9+7;
const int maxn = 4e3 + 12;
char a[maxn][maxn];
bool was[maxn][maxn];
queue<pair<pii, int>> q;
void go(int x, int y, int s){
	q.push({{x, y}, s});
	was[x][y] = 1;
	if(!was[x - 1][y] && a[x][y] == a[x - 1][y])go(x - 1, y, s);
	if(!was[x + 1][y] && a[x][y] == a[x + 1][y])go(x + 1, y, s);
	if(!was[x][y - 1] && a[x][y] == a[x][y - 1])go(x, y - 1, s);
	if(!was[x][y + 1] && a[x][y] == a[x][y + 1])go(x, y + 1, s);	
}
void solve() {
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		was[i][0] = was[i][m + 1] = 1;
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			if(a[i][j] == '.')was[i][j] = 1;
		}
	}
	for(int i = 1; i <= m; i++)was[0][i] = was[n + 1][i] = 1;
	int ans = 0;
	go(n, m, 1);
	while(!q.empty()){
		pair<pii, int> nw = q.front();
		q.pop();
		int x = nw.ff.ff, y = nw.ff.ss, s = nw.ss;
		ans = max(ans, s);
		if(!was[x - 1][y] && a[x][y] != a[x - 1][y])go(x - 1, y, s + 1);
		if(!was[x + 1][y] && a[x][y] != a[x + 1][y])go(x + 1, y, s + 1);
		if(!was[x][y - 1] && a[x][y] != a[x][y - 1])go(x, y - 1, s + 1);
		if(!was[x][y + 1] && a[x][y] != a[x][y + 1])go(x, y + 1, s + 1);
	}
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7256 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 7 ms 9092 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 2 ms 5468 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 3 ms 6744 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct
15 Correct 8 ms 7000 KB Output is correct
16 Correct 10 ms 7196 KB Output is correct
17 Correct 7 ms 7004 KB Output is correct
18 Correct 7 ms 9048 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Correct 33 ms 14328 KB Output is correct
3 Correct 239 ms 41384 KB Output is correct
4 Correct 65 ms 21652 KB Output is correct
5 Correct 124 ms 32568 KB Output is correct
6 Correct 664 ms 187028 KB Output is correct
7 Correct 7 ms 32344 KB Output is correct
8 Correct 6 ms 31832 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 7 ms 32088 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 31 ms 14460 KB Output is correct
14 Correct 19 ms 11608 KB Output is correct
15 Correct 18 ms 11752 KB Output is correct
16 Correct 15 ms 7724 KB Output is correct
17 Correct 81 ms 21952 KB Output is correct
18 Correct 69 ms 21584 KB Output is correct
19 Correct 61 ms 21584 KB Output is correct
20 Correct 52 ms 19540 KB Output is correct
21 Correct 136 ms 32916 KB Output is correct
22 Correct 125 ms 32592 KB Output is correct
23 Correct 145 ms 28268 KB Output is correct
24 Correct 127 ms 32824 KB Output is correct
25 Correct 291 ms 41448 KB Output is correct
26 Runtime error 708 ms 1048576 KB Execution killed with signal 9
27 Correct 797 ms 488436 KB Output is correct
28 Correct 647 ms 178584 KB Output is correct
29 Correct 633 ms 166592 KB Output is correct
30 Correct 646 ms 272020 KB Output is correct
31 Correct 353 ms 31828 KB Output is correct
32 Correct 841 ms 582116 KB Output is correct