Submission #535474

#	Time	Username	Problem	Language	Result	Execution time	Memory
535474		dozer	Tracks in the Snow (BOI13_tracks)	C++14	78.13 / 100	1176 ms	1048576 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], col[N], dist[N];
unordered_map<char, int> value;
 
 
int32_t main()
{
	fastio();
	/*
	#ifndef ONLINE_JUDGE
	fileio();
	#endif
 */
 
	//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];
			id[i][j] = ctr;
			col[id[i][j]] = arr[i][j];
			ctr++;
		}
	}
 
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			if (arr[i][j] == 3) continue;
			int color = arr[i][j];
			if (i < h && arr[i + 1][j] != 3) 
			{
				adj[id[i][j]].pb(id[i + 1][j]);
				adj[id[i + 1][j]].pb(id[i][j]);
			}
			if (j < w && arr[i][j + 1] != 3) 
			{
				adj[id[i][j]].pb(id[i][j + 1]);
				adj[id[i][j + 1]].pb(id[i][j]);
			}
		}
	}
 
	int color = col[1], ans = 0;
 
	deque<int> q;
	memset(dist, modulo, sizeof(dist));
 
	q.push_front(1);
	dist[1] = 1;
 
	int steps = 0;
	while(!q.empty())
	{
		steps++;
		int top = q.front();
		q.pop_front();
		ans = max(ans, dist[top]);
		for (int k = 0; k < adj[top].size(); k++)
		{
			int curr = adj[top][k];
			int d = ((col[top] == col[curr]) ? 0 : 1);
			if (d == 0 && dist[curr] > dist[top]) 
			{
				dist[curr] = dist[top];
				q.push_front(curr);
			}
			else if (dist[curr] > dist[top] + 1)
			{
				dist[curr] = dist[top] + 1;
				q.push_back(curr);
			}
		}
	}
 
	//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:67:8: warning: unused variable 'color' [-Wunused-variable]
   67 |    int color = arr[i][j];
      |        ^~~~~
tracks.cpp:96:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (int k = 0; k < adj[top].size(); k++)
      |                   ~~^~~~~~~~~~~~~~~~~
tracks.cpp:81:6: warning: unused variable 'color' [-Wunused-variable]
   81 |  int color = col[1], ans = 0;
      |      ^~~~~

• Subtask 1: 30 / 30
• Subtask 2: 48.125 / 70