Submission #535459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535459	2022-03-10T09:50:41 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();
	/*
	#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();
		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<<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: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:94:7: warning: unused variable 'tmpdist' [-Wunused-variable]
   94 |   int tmpdist = -q.top().st;
      |       ^~~~~~~
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	339 ms	562672 KB	Output is correct
2	Correct	264 ms	548432 KB	Output is correct
3	Correct	255 ms	548672 KB	Output is correct
4	Correct	315 ms	559276 KB	Output is correct
5	Correct	264 ms	552336 KB	Output is correct
6	Correct	268 ms	548376 KB	Output is correct
7	Correct	255 ms	548728 KB	Output is correct
8	Correct	260 ms	548892 KB	Output is correct
9	Correct	313 ms	549196 KB	Output is correct
10	Correct	261 ms	552072 KB	Output is correct
11	Correct	290 ms	551688 KB	Output is correct
12	Correct	282 ms	554328 KB	Output is correct
13	Correct	281 ms	552172 KB	Output is correct
14	Correct	268 ms	552248 KB	Output is correct
15	Correct	328 ms	561252 KB	Output is correct
16	Correct	325 ms	562740 KB	Output is correct
17	Correct	306 ms	558408 KB	Output is correct
18	Correct	311 ms	559388 KB	Output is correct

Subtask #2

50.3125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	278 ms	580020 KB	Output is correct
2	Correct	469 ms	598692 KB	Output is correct
3	Correct	1312 ms	861672 KB	Output is correct
4	Correct	622 ms	629200 KB	Output is correct
5	Correct	923 ms	823900 KB	Output is correct
6	Runtime error	1846 ms	1048576 KB	Execution killed with signal 9
7	Correct	313 ms	581444 KB	Output is correct
8	Correct	296 ms	580032 KB	Output is correct
9	Correct	341 ms	549972 KB	Output is correct
10	Correct	301 ms	548960 KB	Output is correct
11	Correct	302 ms	580700 KB	Output is correct
12	Correct	352 ms	550044 KB	Output is correct
13	Correct	511 ms	598696 KB	Output is correct
14	Correct	439 ms	578936 KB	Output is correct
15	Correct	399 ms	577900 KB	Output is correct
16	Correct	411 ms	570732 KB	Output is correct
17	Correct	857 ms	667836 KB	Output is correct
18	Correct	707 ms	649840 KB	Output is correct
19	Correct	625 ms	629204 KB	Output is correct
20	Correct	615 ms	634052 KB	Output is correct
21	Correct	932 ms	758892 KB	Output is correct
22	Correct	975 ms	823916 KB	Output is correct
23	Correct	1445 ms	764396 KB	Output is correct
24	Correct	879 ms	779552 KB	Output is correct
25	Execution timed out	2144 ms	884592 KB	Time limit exceeded
26	Runtime error	1700 ms	1048576 KB	Execution killed with signal 9
27	Runtime error	1815 ms	1048576 KB	Execution killed with signal 9
28	Runtime error	1875 ms	1048576 KB	Execution killed with signal 9
29	Runtime error	1885 ms	1048576 KB	Execution killed with signal 9
30	Runtime error	1843 ms	1048576 KB	Execution killed with signal 9
31	Execution timed out	2157 ms	1014604 KB	Time limit exceeded
32	Runtime error	1821 ms	1048576 KB	Execution killed with signal 9