Submission #535474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535474	2022-03-10T10:48:15 Z	dozer	Tracks in the Snow (BOI13_tracks)	C++14	78.125 / 100	1176 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 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 (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	305 ms	584572 KB	Output is correct
2	Correct	262 ms	564028 KB	Output is correct
3	Correct	267 ms	564328 KB	Output is correct
4	Correct	310 ms	579000 KB	Output is correct
5	Correct	268 ms	568888 KB	Output is correct
6	Correct	255 ms	564076 KB	Output is correct
7	Correct	263 ms	564468 KB	Output is correct
8	Correct	262 ms	564700 KB	Output is correct
9	Correct	264 ms	564968 KB	Output is correct
10	Correct	266 ms	568552 KB	Output is correct
11	Correct	272 ms	568384 KB	Output is correct
12	Correct	279 ms	572188 KB	Output is correct
13	Correct	265 ms	568956 KB	Output is correct
14	Correct	265 ms	568844 KB	Output is correct
15	Correct	301 ms	582092 KB	Output is correct
16	Correct	304 ms	584504 KB	Output is correct
17	Correct	296 ms	577888 KB	Output is correct
18	Correct	286 ms	578904 KB	Output is correct

Subtask #2

48.125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	273 ms	596428 KB	Output is correct
2	Correct	414 ms	639040 KB	Output is correct
3	Runtime error	1006 ms	1048576 KB	Execution killed with signal 9
4	Correct	511 ms	689236 KB	Output is correct
5	Correct	870 ms	941840 KB	Output is correct
6	Runtime error	1092 ms	1048576 KB	Execution killed with signal 9
7	Correct	285 ms	597708 KB	Output is correct
8	Correct	277 ms	596460 KB	Output is correct
9	Correct	270 ms	566524 KB	Output is correct
10	Correct	261 ms	564848 KB	Output is correct
11	Correct	281 ms	596972 KB	Output is correct
12	Correct	260 ms	565964 KB	Output is correct
13	Correct	416 ms	640084 KB	Output is correct
14	Correct	346 ms	609212 KB	Output is correct
15	Correct	349 ms	604860 KB	Output is correct
16	Correct	340 ms	598112 KB	Output is correct
17	Correct	648 ms	748364 KB	Output is correct
18	Correct	585 ms	710252 KB	Output is correct
19	Correct	500 ms	689408 KB	Output is correct
20	Correct	466 ms	696780 KB	Output is correct
21	Correct	783 ms	900544 KB	Output is correct
22	Correct	833 ms	941900 KB	Output is correct
23	Correct	1022 ms	908840 KB	Output is correct
24	Correct	753 ms	898252 KB	Output is correct
25	Runtime error	948 ms	1048576 KB	Execution killed with signal 9
26	Runtime error	1034 ms	1048576 KB	Execution killed with signal 9
27	Runtime error	992 ms	1048576 KB	Execution killed with signal 9
28	Runtime error	1018 ms	1048576 KB	Execution killed with signal 9
29	Runtime error	1025 ms	1048576 KB	Execution killed with signal 9
30	Runtime error	1027 ms	1048576 KB	Execution killed with signal 9
31	Runtime error	1176 ms	1048576 KB	Execution killed with signal 9
32	Runtime error	1045 ms	1048576 KB	Execution killed with signal 9