Submission #535490

#	Time	Username	Problem	Language	Result	Execution time	Memory
535490		dozer	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1727 ms	958764 KiB

tracks

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70