제출 #535459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535459		dozer	Tracks in the Snow (BOI13_tracks)	C++14	80.31 / 100	2157 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 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();
		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<<ans<<endl;
	cerr<<"time taken : "<<(float) clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0;
}

컴파일 시 표준 에러 (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: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:94:7: warning: unused variable 'tmpdist' [-Wunused-variable]
   94 |   int tmpdist = -q.top().st;
      |       ^~~~~~~
tracks.cpp:81:6: warning: unused variable 'color' [-Wunused-variable]
   81 |  int color = col[1], ans = 0;
      |      ^~~~~

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