oj.uz

Submission #535449

# Submission time Handle Problem Language Result Execution time Memory
535449 2022-03-10T09:43:35 Z dozer Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 322 ms 548448 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 20000005
#define st first
#define nd second
//#define int long long
#define pii pair<int, int>

vector<int> adj[N];
int id[5015][5015], arr[5015][5015], 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

tracks.cpp: In function 'int32_t main()':
tracks.cpp:69:8: warning: unused variable 'color' [-Wunused-variable]
   69 |    int color = arr[i][j];
      |        ^~~~~
tracks.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int k = 0; k < adj[top].size(); k++)
      |                   ~~^~~~~~~~~~~~~~~~~
tracks.cpp:84:6: warning: unused variable 'color' [-Wunused-variable]
   84 |  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:26:2: note: in expansion of macro 'fileio'
   26 |  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:26:2: note: in expansion of macro 'fileio'
   26 |  fileio();
      |  ^~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 548288 KB Output isn't correct
2 Incorrect 242 ms 548224 KB Output isn't correct
3 Incorrect 257 ms 548332 KB Output isn't correct
4 Incorrect 278 ms 548220 KB Output isn't correct
5 Incorrect 262 ms 548328 KB Output isn't correct
6 Incorrect 264 ms 548260 KB Output isn't correct
7 Incorrect 258 ms 548328 KB Output isn't correct
8 Incorrect 270 ms 548320 KB Output isn't correct
9 Incorrect 268 ms 548448 KB Output isn't correct
10 Incorrect 278 ms 548256 KB Output isn't correct
11 Incorrect 267 ms 548300 KB Output isn't correct
12 Incorrect 249 ms 548212 KB Output isn't correct
13 Incorrect 290 ms 548300 KB Output isn't correct
14 Incorrect 255 ms 548284 KB Output isn't correct
15 Incorrect 263 ms 548332 KB Output isn't correct
16 Incorrect 244 ms 548272 KB Output isn't correct
17 Incorrect 255 ms 548448 KB Output isn't correct
18 Incorrect 254 ms 548292 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 548220 KB Output isn't correct
2 Incorrect 272 ms 548360 KB Output isn't correct
3 Incorrect 243 ms 548320 KB Output isn't correct
4 Incorrect 289 ms 548224 KB Output isn't correct
5 Incorrect 254 ms 548300 KB Output isn't correct
6 Incorrect 252 ms 548216 KB Output isn't correct
7 Incorrect 288 ms 548228 KB Output isn't correct
8 Incorrect 249 ms 548324 KB Output isn't correct
9 Incorrect 288 ms 548304 KB Output isn't correct
10 Incorrect 273 ms 548228 KB Output isn't correct
11 Incorrect 263 ms 548272 KB Output isn't correct
12 Incorrect 289 ms 548444 KB Output isn't correct
13 Incorrect 271 ms 548300 KB Output isn't correct
14 Incorrect 289 ms 548228 KB Output isn't correct
15 Incorrect 266 ms 548288 KB Output isn't correct
16 Incorrect 266 ms 548304 KB Output isn't correct
17 Incorrect 309 ms 548324 KB Output isn't correct
18 Incorrect 300 ms 548328 KB Output isn't correct
19 Incorrect 271 ms 548324 KB Output isn't correct
20 Incorrect 294 ms 548216 KB Output isn't correct
21 Incorrect 309 ms 548216 KB Output isn't correct
22 Incorrect 287 ms 548232 KB Output isn't correct
23 Incorrect 297 ms 548312 KB Output isn't correct
24 Incorrect 285 ms 548264 KB Output isn't correct
25 Incorrect 274 ms 548328 KB Output isn't correct
26 Incorrect 322 ms 548320 KB Output isn't correct
27 Incorrect 295 ms 548276 KB Output isn't correct
28 Incorrect 322 ms 548204 KB Output isn't correct
29 Incorrect 262 ms 548272 KB Output isn't correct
30 Incorrect 269 ms 548232 KB Output isn't correct
31 Incorrect 270 ms 548320 KB Output isn't correct
32 Incorrect 286 ms 548328 KB Output isn't correct