Submission #442016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442016	2021-07-06T18:15:30 Z	Yomapeed	Zoo (COCI19_zoo)	C++17	110 / 110	452 ms	82204 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 + 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

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.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	26700 KB	Output is correct
2	Correct	16 ms	26828 KB	Output is correct
3	Correct	17 ms	26772 KB	Output is correct
4	Correct	16 ms	27028 KB	Output is correct
5	Correct	17 ms	27324 KB	Output is correct
6	Correct	17 ms	27340 KB	Output is correct
7	Correct	17 ms	27340 KB	Output is correct
8	Correct	19 ms	27648 KB	Output is correct
9	Correct	19 ms	27616 KB	Output is correct
10	Correct	20 ms	27852 KB	Output is correct
11	Correct	20 ms	27620 KB	Output is correct
12	Correct	19 ms	27756 KB	Output is correct
13	Correct	18 ms	27532 KB	Output is correct
14	Correct	19 ms	27576 KB	Output is correct
15	Correct	18 ms	27416 KB	Output is correct

Subtask #2

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	26700 KB	Output is correct
2	Correct	16 ms	26828 KB	Output is correct
3	Correct	17 ms	26772 KB	Output is correct
4	Correct	16 ms	27028 KB	Output is correct
5	Correct	17 ms	27324 KB	Output is correct
6	Correct	17 ms	27340 KB	Output is correct
7	Correct	17 ms	27340 KB	Output is correct
8	Correct	19 ms	27648 KB	Output is correct
9	Correct	19 ms	27616 KB	Output is correct
10	Correct	20 ms	27852 KB	Output is correct
11	Correct	20 ms	27620 KB	Output is correct
12	Correct	19 ms	27756 KB	Output is correct
13	Correct	18 ms	27532 KB	Output is correct
14	Correct	19 ms	27576 KB	Output is correct
15	Correct	18 ms	27416 KB	Output is correct
16	Correct	32 ms	34756 KB	Output is correct
17	Correct	35 ms	34948 KB	Output is correct
18	Correct	32 ms	34812 KB	Output is correct
19	Correct	38 ms	35660 KB	Output is correct
20	Correct	34 ms	34892 KB	Output is correct
21	Correct	418 ms	78836 KB	Output is correct
22	Correct	415 ms	79436 KB	Output is correct
23	Correct	422 ms	80004 KB	Output is correct
24	Correct	448 ms	82204 KB	Output is correct
25	Correct	431 ms	81264 KB	Output is correct
26	Correct	427 ms	80516 KB	Output is correct
27	Correct	420 ms	79428 KB	Output is correct
28	Correct	420 ms	79224 KB	Output is correct
29	Correct	440 ms	81936 KB	Output is correct
30	Correct	452 ms	81208 KB	Output is correct