oj.uz

Submission #910924

# Submission time Handle Problem Language Result Execution time Memory
910924 2024-01-18T09:42:11 Z oblantis Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 969 ms 1048576 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];
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 10 ms 7260 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 4572 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 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 3 ms 5468 KB Output is correct
12 Correct 4 ms 6884 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct
15 Correct 9 ms 7004 KB Output is correct
16 Correct 10 ms 7248 KB Output is correct
17 Correct 7 ms 7004 KB Output is correct
18 Correct 7 ms 8540 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31836 KB Output is correct
2 Correct 33 ms 14080 KB Output is correct
3 Correct 231 ms 41044 KB Output is correct
4 Correct 64 ms 21504 KB Output is correct
5 Correct 131 ms 32648 KB Output is correct
6 Correct 651 ms 152284 KB Output is correct
7 Correct 8 ms 32088 KB Output is correct
8 Correct 7 ms 31836 KB Output is correct
9 Correct 2 ms 3100 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 6 ms 31836 KB Output is correct
12 Correct 2 ms 4692 KB Output is correct
13 Correct 33 ms 14232 KB Output is correct
14 Correct 21 ms 11868 KB Output is correct
15 Correct 21 ms 11828 KB Output is correct
16 Correct 17 ms 7516 KB Output is correct
17 Correct 86 ms 21864 KB Output is correct
18 Correct 71 ms 21796 KB Output is correct
19 Correct 65 ms 21400 KB Output is correct
20 Correct 53 ms 19288 KB Output is correct
21 Correct 139 ms 32628 KB Output is correct
22 Correct 123 ms 32336 KB Output is correct
23 Correct 150 ms 27732 KB Output is correct
24 Correct 130 ms 32396 KB Output is correct
25 Correct 326 ms 41080 KB Output is correct
26 Runtime error 765 ms 1048576 KB Execution killed with signal 9
27 Correct 891 ms 441808 KB Output is correct
28 Correct 663 ms 152052 KB Output is correct
29 Correct 647 ms 143472 KB Output is correct
30 Correct 735 ms 238792 KB Output is correct
31 Correct 394 ms 36504 KB Output is correct
32 Correct 969 ms 539920 KB Output is correct