Submission #535461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535461	2022-03-10T09:58:30 Z	dozer	Tracks in the Snow (BOI13_tracks)	C++14	80.3125 / 100	2000 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 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();

 
 
	//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:64:8: warning: unused variable 'color' [-Wunused-variable]
   64 |    int color = arr[i][j];
      |        ^~~~~
tracks.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int k = 0; k < adj[top].size(); k++)
      |                   ~~^~~~~~~~~~~~~~~~~
tracks.cpp:78:6: warning: unused variable 'color' [-Wunused-variable]
   78 |  int color = col[1], ans = 0;
      |      ^~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	331 ms	562584 KB	Output is correct
2	Correct	287 ms	548440 KB	Output is correct
3	Correct	278 ms	548700 KB	Output is correct
4	Correct	314 ms	559052 KB	Output is correct
5	Correct	291 ms	552176 KB	Output is correct
6	Correct	272 ms	548448 KB	Output is correct
7	Correct	272 ms	548728 KB	Output is correct
8	Correct	279 ms	548964 KB	Output is correct
9	Correct	263 ms	549232 KB	Output is correct
10	Correct	291 ms	551872 KB	Output is correct
11	Correct	316 ms	551548 KB	Output is correct
12	Correct	312 ms	554200 KB	Output is correct
13	Correct	304 ms	552164 KB	Output is correct
14	Correct	303 ms	552232 KB	Output is correct
15	Correct	346 ms	561164 KB	Output is correct
16	Correct	362 ms	562636 KB	Output is correct
17	Correct	328 ms	558484 KB	Output is correct
18	Correct	329 ms	559088 KB	Output is correct

Subtask #2

50.3125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	292 ms	580024 KB	Output is correct
2	Correct	418 ms	598616 KB	Output is correct
3	Correct	1245 ms	858316 KB	Output is correct
4	Correct	627 ms	627600 KB	Output is correct
5	Correct	985 ms	820700 KB	Output is correct
6	Runtime error	1907 ms	1048576 KB	Execution killed with signal 9
7	Correct	328 ms	581320 KB	Output is correct
8	Correct	305 ms	580104 KB	Output is correct
9	Correct	328 ms	549896 KB	Output is correct
10	Correct	339 ms	548896 KB	Output is correct
11	Correct	312 ms	580684 KB	Output is correct
12	Correct	327 ms	550016 KB	Output is correct
13	Correct	422 ms	597704 KB	Output is correct
14	Correct	388 ms	578616 KB	Output is correct
15	Correct	372 ms	577508 KB	Output is correct
16	Correct	378 ms	570656 KB	Output is correct
17	Correct	693 ms	664404 KB	Output is correct
18	Correct	643 ms	646480 KB	Output is correct
19	Correct	540 ms	626092 KB	Output is correct
20	Correct	504 ms	631276 KB	Output is correct
21	Correct	841 ms	754268 KB	Output is correct
22	Correct	903 ms	819144 KB	Output is correct
23	Correct	1049 ms	759584 KB	Output is correct
24	Correct	790 ms	774888 KB	Output is correct
25	Execution timed out	2136 ms	879912 KB	Time limit exceeded
26	Runtime error	1724 ms	1048576 KB	Execution killed with signal 9
27	Runtime error	1821 ms	1048576 KB	Execution killed with signal 9
28	Runtime error	1772 ms	1048576 KB	Execution killed with signal 9
29	Runtime error	1746 ms	1048576 KB	Execution killed with signal 9
30	Runtime error	1682 ms	1048576 KB	Execution killed with signal 9
31	Execution timed out	2146 ms	1008864 KB	Time limit exceeded
32	Runtime error	1674 ms	1048576 KB	Execution killed with signal 9