oj.uz

Submission #321498

# Submission time Handle Problem Language Result Execution time Memory
321498 2020-11-12T15:11:27 Z ronnith Zoo (COCI19_zoo) C++14
110 / 110
 64 ms 10220 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORd(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL 
	#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
	#define dbg2(a,b) dbg(a);dbg(b)
	#define dbg3(a,b,c) dbg2(a,b);dbg(c)
	#define dln cerr << ln
#else
	#define dbg(x) 0
	#define dbg2(a,b) 0
	#define dbg3(a,b,c) 0
	#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;

template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

/*OUTPUT

*/

#define maxn 1000

int N, M, vis[maxn][maxn], level[maxn][maxn];
char a[maxn][maxn];

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};

void solve(){
	cin >> N >> M;
	FOR(i,0,N)
		FOR(j,0,M)
			cin >> a[i][j];
	deque<pii> q;
	q.push_back(mk(0,0));
	vis[0][0] = 1;
	while(sz(q))
	{
		auto x = q.front();
		q.pop_front();
		FOR(i,0,4)
		{
			int ii = x.f + dx[i],jj = x.s + dy[i];
			if(ii >= N or ii < 0 or jj >= M or jj < 0)continue;
			if(a[ii][jj] == '*' or vis[ii][jj] == 1)continue;
			if(a[x.f][x.s] == a[ii][jj])
			{
				q.push_front(mk(ii,jj));
				vis[ii][jj] = 1;
				level[ii][jj] = level[x.f][x.s];
			}
			else
			{
				q.push_back(mk(ii,jj));
				vis[ii][jj] = 1;
				level[ii][jj] = level[x.f][x.s] + 1;
			}
		}
	}
	int ans = 0;
	FOR(i,0,N)
		FOR(j,0,M)
		{
			maxs(ans,level[i][j]);
		}
	cout << ans + 1 << '\n';
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		solve();
	}
}

Compilation message

zoo.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
    4 | #warning Check Integer OverFlow
      |  ^~~~~~~

Subtask #1
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 2 ms 1264 KB Output is correct
11 Correct 1 ms 1132 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 1 ms 1004 KB Output is correct
14 Correct 1 ms 1260 KB Output is correct
15 Correct 1 ms 1004 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 2 ms 1264 KB Output is correct
11 Correct 1 ms 1132 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 1 ms 1004 KB Output is correct
14 Correct 1 ms 1260 KB Output is correct
15 Correct 1 ms 1004 KB Output is correct
16 Correct 24 ms 10092 KB Output is correct
17 Correct 25 ms 9984 KB Output is correct
18 Correct 26 ms 10220 KB Output is correct
19 Correct 27 ms 9964 KB Output is correct
20 Correct 26 ms 9836 KB Output is correct
21 Correct 64 ms 9836 KB Output is correct
22 Correct 58 ms 9720 KB Output is correct
23 Correct 60 ms 9836 KB Output is correct
24 Correct 64 ms 10092 KB Output is correct
25 Correct 62 ms 10220 KB Output is correct
26 Correct 60 ms 9708 KB Output is correct
27 Correct 61 ms 9708 KB Output is correct
28 Correct 58 ms 9728 KB Output is correct
29 Correct 62 ms 10092 KB Output is correct
30 Correct 63 ms 9836 KB Output is correct