oj.uz

Submission #910618

# Submission time Handle Problem Language Result Execution time Memory
910618 2024-01-18T06:24:42 Z oblantis Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 898 ms 1048576 KB 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-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 + 1;
char a[maxn][maxn];
bool was[maxn][maxn];
queue<pii> q;
void go(int x, int y, char s){
	if(a[x][y] != s)return;
	q.push({x, y});
	was[x][y] = 1;
	if(!was[x - 1][y])go(x - 1, y, s);
	if(!was[x + 1][y])go(x + 1, y, s);
	if(!was[x][y - 1])go(x, y - 1, s);
	if(!was[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;
	char s = a[n][m];
	go(n, m, s);
	while(!q.empty()){
		pii nw = q.front();
		q.pop();
		int x = nw.ff, y = nw.ss;
		if(a[x][y] == s){
			ans++, s = (s == 'R' ? 'F' : 'R');
		}
		if(!was[x - 1][y])go(x - 1, y, s);
		if(!was[x + 1][y])go(x + 1, y, s);
		if(!was[x][y - 1])go(x, y - 1, s);
		if(!was[x][y + 1])go(x, y + 1, s);
	}
	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 11 ms 7260 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 4568 KB Output is correct
4 Correct 7 ms 8540 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 1 ms 4952 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 4 ms 6744 KB Output is correct
11 Correct 3 ms 5348 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct
15 Correct 8 ms 7212 KB Output is correct
16 Correct 10 ms 7260 KB Output is correct
17 Correct 8 ms 7004 KB Output is correct
18 Correct 8 ms 8540 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31832 KB Output is correct
2 Correct 33 ms 14172 KB Output is correct
3 Correct 228 ms 40884 KB Output is correct
4 Correct 65 ms 21796 KB Output is correct
5 Correct 129 ms 32900 KB Output is correct
6 Correct 626 ms 152048 KB Output is correct
7 Correct 6 ms 32092 KB Output is correct
8 Correct 6 ms 31836 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 6 ms 31704 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 32 ms 14224 KB Output is correct
14 Correct 19 ms 11656 KB Output is correct
15 Correct 19 ms 11612 KB Output is correct
16 Correct 16 ms 7768 KB Output is correct
17 Correct 85 ms 22072 KB Output is correct
18 Correct 74 ms 22052 KB Output is correct
19 Correct 64 ms 21548 KB Output is correct
20 Correct 52 ms 19284 KB Output is correct
21 Correct 143 ms 33112 KB Output is correct
22 Correct 123 ms 33004 KB Output is correct
23 Correct 151 ms 28228 KB Output is correct
24 Correct 128 ms 33108 KB Output is correct
25 Correct 293 ms 41020 KB Output is correct
26 Runtime error 704 ms 1048576 KB Execution killed with signal 9
27 Correct 824 ms 433732 KB Output is correct
28 Correct 629 ms 144152 KB Output is correct
29 Correct 607 ms 135420 KB Output is correct
30 Correct 675 ms 230648 KB Output is correct
31 Correct 366 ms 30844 KB Output is correct
32 Correct 898 ms 531764 KB Output is correct