Submission #535457

#	Time	Username	Problem	Language	Result	Execution time	Memory
535457		dozer	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	355 ms	548416 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 20000005
#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;

	priority_queue<pair<int ,int>> q;
	memset(dist, modulo, sizeof(dist));

	q.push({0, 1});
	dist[1] = 1;

	int steps = 0;
	while(!q.empty())
	{
		steps++;
		int top = q.top().nd;
		int tmpdist = -q.top().st;
		q.pop();
		if (tmpdist > dist[top]) continue;
		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 (dist[curr] > dist[top] + d)
			{
				dist[curr] = dist[top] + d;
				q.push({-dist[curr], 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:66:8: warning: unused variable 'color' [-Wunused-variable]
   66 |    int color = arr[i][j];
      |        ^~~~~
tracks.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int k = 0; k < adj[top].size(); k++)
      |                   ~~^~~~~~~~~~~~~~~~~
tracks.cpp:80:6: warning: unused variable 'color' [-Wunused-variable]
   80 |  int color = col[1], ans = 0;
      |      ^~~~~
tracks.cpp:3:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:25:2: note: in expansion of macro 'fileio'
   25 |  fileio();
      |  ^~~~~~
tracks.cpp:3:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:25:2: note: in expansion of macro 'fileio'
   25 |  fileio();
      |  ^~~~~~

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