oj.uz

Submission #910932

# Submission time Handle Problem Language Result Execution time Memory
910932 2024-01-18T09:48:58 Z oblantis Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 502 ms 148952 KB 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-all-loops")
#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 pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 4e3 + 2;
char a[maxn][maxn];
bool was[maxn][maxn];
int dp[maxn][maxn];
deque<pii> q;
void go(int x, int y, char s, int wt){
	if(a[x][y] != s)dp[x][y] = wt + 1, q.push_back({x, y});
	else dp[x][y] = wt, q.push_front({x, y});
	was[x][y] = 1;
}
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 = 1;
	char s = a[n][m];
	go(n, m, s, 1);
	while(!q.empty()){
		pii nw = q.front();
		q.pop_front();
		int x = nw.ff, y = nw.ss;
		ans = dp[x][y];
		s = a[x][y];
		if(!was[x - 1][y])go(x - 1, y, s, ans);
		if(!was[x + 1][y])go(x + 1, y, s, ans);
		if(!was[x][y - 1])go(x, y - 1, s, ans);
		if(!was[x][y + 1])go(x, y + 1, s, ans);
	}
	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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17244 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 7 ms 17244 KB Output is correct
5 Correct 4 ms 12888 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 5 ms 12892 KB Output is correct
13 Correct 4 ms 12888 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 9 ms 17124 KB Output is correct
16 Correct 10 ms 17244 KB Output is correct
17 Correct 8 ms 16988 KB Output is correct
18 Correct 7 ms 17244 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 93532 KB Output is correct
2 Correct 38 ms 34640 KB Output is correct
3 Correct 225 ms 102608 KB Output is correct
4 Correct 74 ms 52048 KB Output is correct
5 Correct 127 ms 79104 KB Output is correct
6 Correct 502 ms 115216 KB Output is correct
7 Correct 17 ms 94552 KB Output is correct
8 Correct 16 ms 93544 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 17 ms 94096 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 32 ms 34412 KB Output is correct
14 Correct 22 ms 25692 KB Output is correct
15 Correct 24 ms 30292 KB Output is correct
16 Correct 14 ms 13400 KB Output is correct
17 Correct 77 ms 54096 KB Output is correct
18 Correct 88 ms 54104 KB Output is correct
19 Correct 76 ms 52172 KB Output is correct
20 Correct 62 ms 47952 KB Output is correct
21 Correct 134 ms 83168 KB Output is correct
22 Correct 127 ms 79188 KB Output is correct
23 Correct 151 ms 68432 KB Output is correct
24 Correct 135 ms 83496 KB Output is correct
25 Correct 458 ms 102484 KB Output is correct
26 Correct 281 ms 148952 KB Output is correct
27 Correct 345 ms 114380 KB Output is correct
28 Correct 482 ms 106872 KB Output is correct
29 Correct 457 ms 105636 KB Output is correct
30 Correct 428 ms 111312 KB Output is correct
31 Correct 330 ms 81236 KB Output is correct
32 Correct 363 ms 114960 KB Output is correct