oj.uz

Submission #711177

# Submission time Handle Problem Language Result Execution time Memory
711177 2023-03-16T09:24:27 Z dozer Zoo (COCI19_zoo) C++14
110 / 110
 324 ms 459008 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#define fastio() ios_base::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define ll long long
#define sp " "
#define endl "\n"
#define modulo 100000007
#define N 18000005
#define st first
#define nd second
#define int long long
#define pii pair<int, int>
 
vector<int> adj[N];
int id[4005][4005], arr[4015][4005], dist[4005][4005], vis[4005][4005];
unordered_map<char, int> value;
 
 
int32_t main()
{
	fastio();
 
	//cout<<(((4005 * 4005 * 2) + 6 * N) * 4)/ (1<<20)<<endl;
	int h, w;
	cin>>h>>w;
 
	value['F'] = 1, value['R'] = 2, value['.'] = 3;
	int ctr = 1;
 
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			char tmp;
			cin>>tmp;
			switch(tmp)
			{
				case 'B':
					arr[i][j] = 1;
					break;
				case 'T':
					arr[i][j] = 2;
					break;
				case '*':
					arr[i][j] = 3;
					break;
			}
			//arr[i][j] = value[tmp];
		}
	}
 
	int color = arr[1][1], ans = 0;
 
	deque<pii> q;
	//memset(dist, modulo, sizeof(dist));
 
	q.push_front({1, 1});
	dist[1][1] = 1;
 
	int steps = 0;
	while(!q.empty())
	{
		steps++;
		pii top = q.front();
		vis[top.st][top.nd] = 1;
		int i = top.st, j = top.nd;
		int d = dist[i][j];
		q.pop_front();
		ans = max(ans, d);
		
		int color = arr[i][j];
		if (i < h && arr[i + 1][j] == color && vis[i + 1][j] == 0) 
			q.push_front({i + 1, j}), dist[i + 1][j] = d;
 
		else if (i < h && arr[i + 1][j] == 3 - color && vis[i + 1][j] == 0) 
			q.push_back({i + 1, j}), dist[i + 1][j] = d + 1; 
 
 		if (i > 1 && arr[i - 1][j] == color && vis[i - 1][j] == 0)
 			q.push_front({i - 1, j}), dist[i - 1][j] = d;
 
		else if (i > 1 && arr[i - 1][j] == 3 - color && vis[i - 1][j] == 0) 
			q.push_back({i - 1, j}), dist[i - 1][j] = d + 1; 
 
 		if (j < w && arr[i][j + 1] == color && vis[i][j + 1] == 0) 
 			q.push_front({i, j + 1}), dist[i][j + 1] = d;
 
		else if (j < w && arr[i][j + 1] == 3 - color && vis[i][j + 1] == 0) 
			q.push_back({i, j + 1}), dist[i][j + 1] = d + 1; 
 
 		if (j > 1 && arr[i][j - 1] == color && vis[i][j - 1] == 0) 
 			q.push_front({i, j - 1}), dist[i][j - 1] = d;
 
		else if (j > 1 && arr[i][j - 1] == 3 - color && vis[i][j - 1] == 0) 
			q.push_back({i, j - 1}), dist[i][j - 1] = d + 1; 
	}
 
	//cout<<steps<<endl;
	cout<<ans<<endl;
	cerr<<"time taken : "<<(float) clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0;
}

Compilation message

zoo.cpp: In function 'int32_t main()':
zoo.cpp:30:6: warning: unused variable 'ctr' [-Wunused-variable]
   30 |  int ctr = 1;
      |      ^~~
zoo.cpp:54:6: warning: unused variable 'color' [-Wunused-variable]
   54 |  int color = arr[1][1], ans = 0;
      |      ^~~~~

Subtask #1
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 423052 KB Output is correct
2 Correct 187 ms 423288 KB Output is correct
3 Correct 201 ms 423348 KB Output is correct
4 Correct 187 ms 423636 KB Output is correct
5 Correct 189 ms 424472 KB Output is correct
6 Correct 208 ms 424412 KB Output is correct
7 Correct 193 ms 424380 KB Output is correct
8 Correct 196 ms 424304 KB Output is correct
9 Correct 193 ms 424248 KB Output is correct
10 Correct 214 ms 424540 KB Output is correct
11 Correct 188 ms 424204 KB Output is correct
12 Correct 192 ms 424456 KB Output is correct
13 Correct 207 ms 424100 KB Output is correct
14 Correct 188 ms 424336 KB Output is correct
15 Correct 189 ms 424044 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 423052 KB Output is correct
2 Correct 187 ms 423288 KB Output is correct
3 Correct 201 ms 423348 KB Output is correct
4 Correct 187 ms 423636 KB Output is correct
5 Correct 189 ms 424472 KB Output is correct
6 Correct 208 ms 424412 KB Output is correct
7 Correct 193 ms 424380 KB Output is correct
8 Correct 196 ms 424304 KB Output is correct
9 Correct 193 ms 424248 KB Output is correct
10 Correct 214 ms 424540 KB Output is correct
11 Correct 188 ms 424204 KB Output is correct
12 Correct 192 ms 424456 KB Output is correct
13 Correct 207 ms 424100 KB Output is correct
14 Correct 188 ms 424336 KB Output is correct
15 Correct 189 ms 424044 KB Output is correct
16 Correct 285 ms 446520 KB Output is correct
17 Correct 226 ms 446416 KB Output is correct
18 Correct 226 ms 446872 KB Output is correct
19 Correct 234 ms 447948 KB Output is correct
20 Correct 212 ms 446420 KB Output is correct
21 Correct 286 ms 457112 KB Output is correct
22 Correct 279 ms 457160 KB Output is correct
23 Correct 324 ms 457584 KB Output is correct
24 Correct 312 ms 459008 KB Output is correct
25 Correct 291 ms 458400 KB Output is correct
26 Correct 310 ms 457876 KB Output is correct
27 Correct 280 ms 457208 KB Output is correct
28 Correct 285 ms 457184 KB Output is correct
29 Correct 284 ms 458744 KB Output is correct
30 Correct 296 ms 458140 KB Output is correct