oj.uz

Submission #535490

# Submission time Handle Problem Language Result Execution time Memory
535490 2022-03-10T11:33:09 Z dozer Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1727 ms 958764 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 'F':
					arr[i][j] = 1;
					break;
				case 'R':
					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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 434892 KB Output is correct
2 Correct 210 ms 423236 KB Output is correct
3 Correct 223 ms 423628 KB Output is correct
4 Correct 221 ms 433396 KB Output is correct
5 Correct 213 ms 428160 KB Output is correct
6 Correct 219 ms 423176 KB Output is correct
7 Correct 209 ms 423560 KB Output is correct
8 Correct 209 ms 423884 KB Output is correct
9 Correct 210 ms 424516 KB Output is correct
10 Correct 213 ms 427072 KB Output is correct
11 Correct 220 ms 426564 KB Output is correct
12 Correct 226 ms 428716 KB Output is correct
13 Correct 231 ms 428204 KB Output is correct
14 Correct 214 ms 428136 KB Output is correct
15 Correct 237 ms 434168 KB Output is correct
16 Correct 240 ms 434824 KB Output is correct
17 Correct 233 ms 434236 KB Output is correct
18 Correct 221 ms 433432 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 470268 KB Output is correct
2 Correct 304 ms 463500 KB Output is correct
3 Correct 726 ms 669876 KB Output is correct
4 Correct 366 ms 530428 KB Output is correct
5 Correct 482 ms 606540 KB Output is correct
6 Correct 1703 ms 871888 KB Output is correct
7 Correct 240 ms 472444 KB Output is correct
8 Correct 229 ms 470448 KB Output is correct
9 Correct 213 ms 424392 KB Output is correct
10 Correct 210 ms 423364 KB Output is correct
11 Correct 226 ms 471428 KB Output is correct
12 Correct 209 ms 425292 KB Output is correct
13 Correct 304 ms 463592 KB Output is correct
14 Correct 258 ms 449244 KB Output is correct
15 Correct 256 ms 458540 KB Output is correct
16 Correct 257 ms 439232 KB Output is correct
17 Correct 428 ms 511216 KB Output is correct
18 Correct 392 ms 541104 KB Output is correct
19 Correct 362 ms 530324 KB Output is correct
20 Correct 328 ms 497032 KB Output is correct
21 Correct 509 ms 591612 KB Output is correct
22 Correct 485 ms 606340 KB Output is correct
23 Correct 636 ms 573644 KB Output is correct
24 Correct 469 ms 587424 KB Output is correct
25 Correct 1110 ms 800980 KB Output is correct
26 Correct 1060 ms 958764 KB Output is correct
27 Correct 1325 ms 891536 KB Output is correct
28 Correct 1706 ms 871724 KB Output is correct
29 Correct 1727 ms 868484 KB Output is correct
30 Correct 1519 ms 875704 KB Output is correct
31 Correct 1654 ms 706480 KB Output is correct
32 Correct 1222 ms 851796 KB Output is correct