Submission #535473

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535473	2022-03-10T10:46:53 Z	dozer	Tracks in the Snow (BOI13_tracks)	C++17	56.25 / 100	807 ms	1048576 KB

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 30000005
#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 (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;
      |      ^~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	492 ms	960452 KB	Output is correct
2	Correct	461 ms	939808 KB	Output is correct
3	Correct	439 ms	940260 KB	Output is correct
4	Correct	468 ms	954784 KB	Output is correct
5	Correct	434 ms	944732 KB	Output is correct
6	Correct	438 ms	939752 KB	Output is correct
7	Correct	439 ms	940152 KB	Output is correct
8	Correct	441 ms	940492 KB	Output is correct
9	Correct	417 ms	940668 KB	Output is correct
10	Correct	456 ms	944396 KB	Output is correct
11	Correct	437 ms	944216 KB	Output is correct
12	Correct	452 ms	948096 KB	Output is correct
13	Correct	451 ms	944740 KB	Output is correct
14	Correct	479 ms	944844 KB	Output is correct
15	Correct	464 ms	958132 KB	Output is correct
16	Correct	502 ms	960436 KB	Output is correct
17	Correct	481 ms	953784 KB	Output is correct
18	Correct	451 ms	954772 KB	Output is correct

Subtask #2

26.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	516 ms	972192 KB	Output is correct
2	Correct	612 ms	1014860 KB	Output is correct
3	Runtime error	640 ms	1048576 KB	Execution killed with signal 9
4	Runtime error	508 ms	1048576 KB	Execution killed with signal 9
5	Runtime error	745 ms	1048576 KB	Execution killed with signal 9
6	Runtime error	656 ms	1048576 KB	Execution killed with signal 9
7	Correct	468 ms	973496 KB	Output is correct
8	Correct	459 ms	972160 KB	Output is correct
9	Correct	449 ms	942320 KB	Output is correct
10	Correct	458 ms	940652 KB	Output is correct
11	Correct	500 ms	972748 KB	Output is correct
12	Correct	430 ms	941768 KB	Output is correct
13	Correct	601 ms	1014744 KB	Output is correct
14	Correct	535 ms	984672 KB	Output is correct
15	Correct	536 ms	980068 KB	Output is correct
16	Correct	555 ms	973716 KB	Output is correct
17	Runtime error	579 ms	1048576 KB	Execution killed with signal 9
18	Runtime error	555 ms	1048576 KB	Execution killed with signal 9
19	Runtime error	547 ms	1048576 KB	Execution killed with signal 9
20	Runtime error	508 ms	1048576 KB	Execution killed with signal 9
21	Runtime error	748 ms	1048576 KB	Execution killed with signal 9
22	Runtime error	762 ms	1048576 KB	Execution killed with signal 9
23	Runtime error	807 ms	1048576 KB	Execution killed with signal 9
24	Runtime error	730 ms	1048576 KB	Execution killed with signal 9
25	Runtime error	660 ms	1048576 KB	Execution killed with signal 9
26	Runtime error	646 ms	1048576 KB	Execution killed with signal 9
27	Runtime error	576 ms	1048576 KB	Execution killed with signal 9
28	Runtime error	602 ms	1048576 KB	Execution killed with signal 9
29	Runtime error	653 ms	1048576 KB	Execution killed with signal 9
30	Runtime error	611 ms	1048576 KB	Execution killed with signal 9
31	Runtime error	734 ms	1048576 KB	Execution killed with signal 9
32	Runtime error	598 ms	1048576 KB	Execution killed with signal 9