Submission #442014

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442014	2021-07-06T18:12:00 Z	Yomapeed	Zoo (COCI19_zoo)	C++17	0 / 110	16 ms	26828 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 dfs2(ll a){
	ll res = 1;
	vis[a] = true;
	for(auto u : adj[a]){
		if(!vis[u]){
			res = max(res, 1 + dfs2(u));
		}
	}
	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 << dfs2(1);
	}
	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

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	26700 KB	Output is correct
2	Correct	16 ms	26740 KB	Output is correct
3	Incorrect	16 ms	26828 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	26700 KB	Output is correct
2	Correct	16 ms	26740 KB	Output is correct
3	Incorrect	16 ms	26828 KB	Output isn't correct
4	Halted	0 ms	0 KB	-