Submission #442016

#	Time	Username	Problem	Language	Result	Execution time	Memory
442016		Yomapeed	Zoo (COCI19_zoo)	C++17	110 / 110	452 ms	82204 KiB

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 + 60;
string s[N]; 
ll n, m;
char c;
ll curr;
bool visited[N][N];
map<pair<ll,ll>, bool> done;
ll val[N][N];
bool vis[N* N];
vector<ll> X = {1, -1, 0, 0};
vector<ll> Y = {0, 0, 1, -1};
vector<ll> adj[N * N];
bool valid(ll x, ll y){
	if(x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '*'){
		return false;
	}
	
	return true;
}
ll cnt = 0;
void dfs(ll a, ll b){
	visited[a][b] = true;
	val[a][b] = curr;
	//cout << a << " $ " << b << endl;
	for(int i = 0; i < 4; i++){
		ll x, y;
		x = a + X[i], y = b + Y[i];
		//cout << x << " #$%$%$% " << y << endl;
		if(!valid(x, y)){
			continue;
		}
		
		if(!visited[x][y] && s[x][y] == s[a][b]){
			dfs(x, y);	
		}
	}

}
ll bfs(){
	queue<pair<ll,ll>> q;
	q.push({1, 1});
	ll res;
	vis[1] = true;
	while(!q.empty()){
		ll a, b;
		tie(a, b) = q.front(); q.pop();
		res = b;
		for(auto u : adj[a]){
			if(!vis[u]){
				q.push({u, b + 1});
				vis[u] = true;
			}
		}
	}
	return res;
}
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];
		}		
		curr = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(s[i][j] == '*'){
					continue;
				}
				if(!visited[i][j]){
					curr++;
					//cout << i << " ################ " << j << endl;
					dfs(i, j);
				}
			}
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(s[i][j] == '*'){
					continue;
				}
				for(int k = 0; k < 4; k++){
					
					ll x = i + X[k];
					ll y = j + Y[k];
					if(valid(x, y) && val[i][j] != val[x][y]){
						ll a, b;
						a = val[x][y];
						b = val[i][j];
						if(done[{a, b}]){
							continue;
						}
						done[{a, b}] = true;
						done[{b, a}] = true;
						adj[a].pb(b);
						adj[b].pb(a);
						//cout << a << " " << b << endl;
					}
				}
			}
		}
		// for(int i = 0; i < n; i++){
		// 	for(int j = 0; j < m; j++){
		// 		cout << val[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }
		cout << bfs();
	}
	return 0;
}

Compilation message (stderr)

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")
      | 
zoo.cpp: In function 'long long int bfs()':
zoo.cpp:78:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |  return res;
      |         ^~~

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65