Submission #441990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441990	2021-07-06T16:18:34 Z	Yomapeed	Zoo (COCI19_zoo)	C++17	45 / 110	2000 ms	11688 KB

zoo

#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 1e3 + 1;
string s[N]; 
ll n, m;
char c;
ll curr;
int visited[N][N];
vector<ll> X = {1, -1, 0, 0};
vector<ll> Y = {0, 0, 1, -1};
bool valid(ll x, ll y){
	if(x < 0 || x >= n || y < 0 || y >= m){
		return false;
	}
	if(s[x][y] == c || s[x][y] == '.'){
		return true;
	}
	return false;
}
ll cnt = 0;
void dfs(ll a, ll b){
	visited[a][b] = curr;
	if(s[a][b] != '.'){
		cnt++;
	}
	s[a][b] = '.';
	for(int i = 0; i < 4; i++){
		ll x, y;
		x = a + X[i], y = b + Y[i];
		if(!valid(x, y)){
			continue;
		}
		if(curr != visited[x][y])
		dfs(x, y);	
	}

}
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	fast;
	ll T = 1;
	
	//cin >> T;
	while (T--) {
		cin >> n >> m;
		for(int i = 0; i < n; i++){
			cin >> s[i];
		}		
		c = s[0][0];
		ll ans = 0;
		while(1){
			cnt = 0;
			// for(int i = 0; i < n; i++){
			// 	for(int j = 0; j < m; j++){
			// 		visited[i][j] = false;
			// 	}
			// }
			curr++;
			dfs(0, 0);
			if(cnt == 0){
				break;
			}
			ans++;
			if(c == 'B'){
				c = 'T';
			}
			else{
				c = 'B';
			}
		}	
		cout << ans << "\n";
	}
	return 0;
}

Compilation message

zoo.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
zoo.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	2 ms	844 KB	Output is correct
7	Correct	2 ms	844 KB	Output is correct
8	Correct	7 ms	716 KB	Output is correct
9	Correct	7 ms	764 KB	Output is correct
10	Correct	9 ms	844 KB	Output is correct
11	Correct	9 ms	716 KB	Output is correct
12	Correct	11 ms	844 KB	Output is correct
13	Correct	7 ms	716 KB	Output is correct
14	Correct	7 ms	716 KB	Output is correct
15	Correct	9 ms	868 KB	Output is correct

Subtask #2

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	2 ms	844 KB	Output is correct
7	Correct	2 ms	844 KB	Output is correct
8	Correct	7 ms	716 KB	Output is correct
9	Correct	7 ms	764 KB	Output is correct
10	Correct	9 ms	844 KB	Output is correct
11	Correct	9 ms	716 KB	Output is correct
12	Correct	11 ms	844 KB	Output is correct
13	Correct	7 ms	716 KB	Output is correct
14	Correct	7 ms	716 KB	Output is correct
15	Correct	9 ms	868 KB	Output is correct
16	Correct	24 ms	6736 KB	Output is correct
17	Correct	26 ms	6836 KB	Output is correct
18	Correct	24 ms	6476 KB	Output is correct
19	Correct	36 ms	7276 KB	Output is correct
20	Correct	25 ms	6236 KB	Output is correct
21	Execution timed out	2087 ms	11688 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-