oj.uz

Submission #910922

# Submission time Handle Problem Language Result Execution time Memory
910922 2024-01-18T09:40:11 Z oblantis Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 993 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 + 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 4700 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 3 ms 6836 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4696 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 5 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 9 ms 7004 KB Output is correct
16 Correct 10 ms 7260 KB Output is correct
17 Correct 9 ms 7152 KB Output is correct
18 Correct 7 ms 8536 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 32 ms 14676 KB Output is correct
3 Correct 245 ms 47696 KB Output is correct
4 Correct 61 ms 23124 KB Output is correct
5 Correct 136 ms 36464 KB Output is correct
6 Correct 682 ms 159324 KB Output is correct
7 Correct 7 ms 32092 KB Output is correct
8 Correct 6 ms 31836 KB Output is correct
9 Correct 3 ms 3164 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 6 ms 31832 KB Output is correct
12 Correct 2 ms 4696 KB Output is correct
13 Correct 38 ms 14952 KB Output is correct
14 Correct 19 ms 11864 KB Output is correct
15 Correct 18 ms 11864 KB Output is correct
16 Correct 17 ms 7516 KB Output is correct
17 Correct 86 ms 23388 KB Output is correct
18 Correct 70 ms 23380 KB Output is correct
19 Correct 62 ms 23124 KB Output is correct
20 Correct 54 ms 20564 KB Output is correct
21 Correct 136 ms 36944 KB Output is correct
22 Correct 131 ms 36480 KB Output is correct
23 Correct 155 ms 31320 KB Output is correct
24 Correct 132 ms 36972 KB Output is correct
25 Correct 322 ms 47696 KB Output is correct
26 Runtime error 776 ms 1048576 KB Execution killed with signal 9
27 Correct 916 ms 451260 KB Output is correct
28 Correct 666 ms 159640 KB Output is correct
29 Correct 646 ms 150180 KB Output is correct
30 Correct 723 ms 245648 KB Output is correct
31 Correct 397 ms 41188 KB Output is correct
32 Correct 993 ms 546360 KB Output is correct