oj.uz

Submission #535457

# Submission time Handle Problem Language Result Execution time Memory
535457 2022-03-10T09:47:23 Z dozer Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 355 ms 548416 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[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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 548248 KB Output isn't correct
2 Incorrect 282 ms 548240 KB Output isn't correct
3 Incorrect 276 ms 548212 KB Output isn't correct
4 Incorrect 267 ms 548308 KB Output isn't correct
5 Incorrect 275 ms 548300 KB Output isn't correct
6 Incorrect 279 ms 548248 KB Output isn't correct
7 Incorrect 276 ms 548304 KB Output isn't correct
8 Incorrect 273 ms 548252 KB Output isn't correct
9 Incorrect 287 ms 548416 KB Output isn't correct
10 Incorrect 271 ms 548296 KB Output isn't correct
11 Incorrect 309 ms 548320 KB Output isn't correct
12 Incorrect 276 ms 548304 KB Output isn't correct
13 Incorrect 276 ms 548300 KB Output isn't correct
14 Incorrect 297 ms 548408 KB Output isn't correct
15 Incorrect 279 ms 548208 KB Output isn't correct
16 Incorrect 291 ms 548300 KB Output isn't correct
17 Incorrect 269 ms 548292 KB Output isn't correct
18 Incorrect 295 ms 548228 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 301 ms 548312 KB Output isn't correct
2 Incorrect 286 ms 548268 KB Output isn't correct
3 Incorrect 286 ms 548332 KB Output isn't correct
4 Incorrect 282 ms 548280 KB Output isn't correct
5 Incorrect 302 ms 548224 KB Output isn't correct
6 Incorrect 281 ms 548308 KB Output isn't correct
7 Incorrect 276 ms 548292 KB Output isn't correct
8 Incorrect 286 ms 548300 KB Output isn't correct
9 Incorrect 263 ms 548352 KB Output isn't correct
10 Incorrect 282 ms 548220 KB Output isn't correct
11 Incorrect 316 ms 548276 KB Output isn't correct
12 Incorrect 279 ms 548244 KB Output isn't correct
13 Incorrect 324 ms 548268 KB Output isn't correct
14 Incorrect 274 ms 548292 KB Output isn't correct
15 Incorrect 256 ms 548296 KB Output isn't correct
16 Incorrect 288 ms 548296 KB Output isn't correct
17 Incorrect 265 ms 548232 KB Output isn't correct
18 Incorrect 290 ms 548300 KB Output isn't correct
19 Incorrect 301 ms 548228 KB Output isn't correct
20 Incorrect 277 ms 548304 KB Output isn't correct
21 Incorrect 277 ms 548216 KB Output isn't correct
22 Incorrect 283 ms 548336 KB Output isn't correct
23 Incorrect 279 ms 548332 KB Output isn't correct
24 Incorrect 280 ms 548236 KB Output isn't correct
25 Incorrect 286 ms 548292 KB Output isn't correct
26 Incorrect 310 ms 548308 KB Output isn't correct
27 Incorrect 256 ms 548332 KB Output isn't correct
28 Incorrect 261 ms 548300 KB Output isn't correct
29 Incorrect 271 ms 548304 KB Output isn't correct
30 Incorrect 269 ms 548212 KB Output isn't correct
31 Incorrect 260 ms 548304 KB Output isn't correct
32 Incorrect 296 ms 548396 KB Output isn't correct