oj.uz

Submission #535476

# Submission time Handle Problem Language Result Execution time Memory
535476 2022-03-10T10:55:20 Z dozer Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1538 ms 1048576 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 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 (d == 1 && 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: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;
      |      ^~~~~
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 Runtime error 1369 ms 1048576 KB Execution killed with signal 11
2 Runtime error 1331 ms 1048576 KB Execution killed with signal 11
3 Runtime error 1325 ms 1048576 KB Execution killed with signal 11
4 Runtime error 1345 ms 1048576 KB Execution killed with signal 11
5 Runtime error 1405 ms 1048576 KB Execution killed with signal 11
6 Runtime error 1367 ms 1048576 KB Execution killed with signal 11
7 Runtime error 1350 ms 1048576 KB Execution killed with signal 11
8 Runtime error 1332 ms 1048576 KB Execution killed with signal 11
9 Runtime error 1420 ms 1048576 KB Execution killed with signal 11
10 Runtime error 1455 ms 1048576 KB Execution killed with signal 11
11 Runtime error 1348 ms 1048576 KB Execution killed with signal 11
12 Runtime error 1388 ms 1048576 KB Execution killed with signal 11
13 Runtime error 1375 ms 1048576 KB Execution killed with signal 11
14 Runtime error 1429 ms 1048576 KB Execution killed with signal 11
15 Runtime error 1354 ms 1048576 KB Execution killed with signal 11
16 Runtime error 1423 ms 1048576 KB Execution killed with signal 11
17 Runtime error 1449 ms 1048576 KB Execution killed with signal 11
18 Runtime error 1356 ms 1048576 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 1390 ms 1048576 KB Execution killed with signal 11
2 Runtime error 1430 ms 1048576 KB Execution killed with signal 11
3 Runtime error 1406 ms 1048576 KB Execution killed with signal 11
4 Runtime error 1419 ms 1048576 KB Execution killed with signal 11
5 Runtime error 1346 ms 1048576 KB Execution killed with signal 11
6 Runtime error 1368 ms 1048576 KB Execution killed with signal 11
7 Runtime error 1392 ms 1048576 KB Execution killed with signal 11
8 Runtime error 1397 ms 1048576 KB Execution killed with signal 11
9 Runtime error 1390 ms 1048576 KB Execution killed with signal 11
10 Runtime error 1404 ms 1048576 KB Execution killed with signal 11
11 Runtime error 1379 ms 1048576 KB Execution killed with signal 11
12 Runtime error 1381 ms 1048576 KB Execution killed with signal 11
13 Runtime error 1410 ms 1048576 KB Execution killed with signal 11
14 Runtime error 1405 ms 1048576 KB Execution killed with signal 11
15 Runtime error 1397 ms 1048576 KB Execution killed with signal 11
16 Runtime error 1330 ms 1048576 KB Execution killed with signal 11
17 Runtime error 1427 ms 1048576 KB Execution killed with signal 11
18 Runtime error 1349 ms 1048576 KB Execution killed with signal 11
19 Runtime error 1538 ms 1048576 KB Execution killed with signal 11
20 Runtime error 1360 ms 1048576 KB Execution killed with signal 11
21 Runtime error 1313 ms 1048576 KB Execution killed with signal 11
22 Runtime error 1374 ms 1048576 KB Execution killed with signal 11
23 Runtime error 1336 ms 1048576 KB Execution killed with signal 11
24 Runtime error 1353 ms 1048576 KB Execution killed with signal 11
25 Runtime error 1345 ms 1048576 KB Execution killed with signal 11
26 Runtime error 1367 ms 1048576 KB Execution killed with signal 11
27 Runtime error 1350 ms 1048576 KB Execution killed with signal 11
28 Runtime error 1359 ms 1048576 KB Execution killed with signal 11
29 Runtime error 1383 ms 1048576 KB Execution killed with signal 11
30 Runtime error 1331 ms 1048576 KB Execution killed with signal 11
31 Runtime error 1383 ms 1048576 KB Execution killed with signal 11
32 Runtime error 1347 ms 1048576 KB Execution killed with signal 11