Submission #111801

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111801	2019-05-16T08:03:40 Z	anayk	Tracks in the Snow (BOI13_tracks)	C++14	78.125 / 100	2000 ms	749320 KB

tracks

#include <iostream>
#include <vector>
#include <deque>

#define MAXN 4005
#define MAXV 17000000

int n, m;
std::vector<std::pair<int, bool> > Adj[MAXV];
int mat[MAXN][MAXN];

int main()
{
	std::cin >> n >> m;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			char c;
			std::cin >> c;
			if(c == 'R')
				mat[i][j] = 1;
			else if(c == 'F')
				mat[i][j] = 2;
			else
				mat[i][j] = 0;
		}
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			int u = i*m + j;
			if(mat[i][j])
			{
				if(i && mat[i-1][j])
				{
					bool type = (mat[i-1][j] != mat[i][j]);
					int v = (i-1)*m + j;
					Adj[u].push_back({v, type});
					Adj[v].push_back({u, type});
				}
				
				if(j && mat[i][j-1])
				{
					bool type = (mat[i][j-1] != mat[i][j]);
					int v = i*m + j - 1;
					Adj[u].push_back({v, type});
					Adj[v].push_back({u, type});
				}
			}
		}
	}
	
	std::deque<int> bfs;
	int d[MAXV];
	bool vis[MAXV];
	d[0] = 0;
	for(int i = 0; i < MAXV; i++)
		vis[i] = false;;
	bfs.push_front(0);
	vis[0] = true;
	
	int answer = 0;
	while(!bfs.empty())
	{
		int u = bfs.front();
		bfs.pop_front();
		for(std::pair<int, bool> v : Adj[u])
		{
			if(!vis[v.first])
			{
				vis[v.first] = true;
				d[v.first] = d[u];
				if(v.second)
				{
					bfs.push_back(v.first);
					d[v.first]++;
				}
				else
					bfs.push_front(v.first);
				answer = std::max(answer, d[v.first]);
			}
		}
	}
	
	std::cout << answer+1 << std::endl;
	
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	779 ms	431056 KB	Output is correct
2	Correct	360 ms	416376 KB	Output is correct
3	Correct	421 ms	416460 KB	Output is correct
4	Correct	438 ms	426728 KB	Output is correct
5	Correct	356 ms	418820 KB	Output is correct
6	Correct	400 ms	416232 KB	Output is correct
7	Correct	410 ms	416476 KB	Output is correct
8	Correct	376 ms	416784 KB	Output is correct
9	Correct	367 ms	416732 KB	Output is correct
10	Correct	393 ms	418808 KB	Output is correct
11	Correct	385 ms	419164 KB	Output is correct
12	Correct	427 ms	421912 KB	Output is correct
13	Correct	406 ms	418680 KB	Output is correct
14	Correct	354 ms	418732 KB	Output is correct
15	Correct	399 ms	428516 KB	Output is correct
16	Correct	423 ms	431096 KB	Output is correct
17	Correct	393 ms	424440 KB	Output is correct
18	Correct	430 ms	426620 KB	Output is correct

Subtask #2

48.125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	432364 KB	Output is correct
2	Correct	834 ms	462156 KB	Output is correct
3	Execution timed out	2083 ms	579036 KB	Time limit exceeded
4	Correct	800 ms	473980 KB	Output is correct
5	Correct	1736 ms	628240 KB	Output is correct
6	Execution timed out	2091 ms	663772 KB	Time limit exceeded
7	Correct	382 ms	433016 KB	Output is correct
8	Correct	412 ms	432348 KB	Output is correct
9	Correct	431 ms	418020 KB	Output is correct
10	Correct	391 ms	416632 KB	Output is correct
11	Correct	445 ms	432504 KB	Output is correct
12	Correct	383 ms	417352 KB	Output is correct
13	Correct	661 ms	462584 KB	Output is correct
14	Correct	516 ms	444088 KB	Output is correct
15	Correct	558 ms	437648 KB	Output is correct
16	Correct	517 ms	438904 KB	Output is correct
17	Correct	1109 ms	526712 KB	Output is correct
18	Correct	1099 ms	490756 KB	Output is correct
19	Correct	915 ms	474224 KB	Output is correct
20	Correct	880 ms	485744 KB	Output is correct
21	Correct	1453 ms	584956 KB	Output is correct
22	Correct	1713 ms	628240 KB	Output is correct
23	Correct	1876 ms	621800 KB	Output is correct
24	Correct	1434 ms	579004 KB	Output is correct
25	Execution timed out	2106 ms	643248 KB	Time limit exceeded
26	Execution timed out	2131 ms	710668 KB	Time limit exceeded
27	Execution timed out	2103 ms	712628 KB	Time limit exceeded
28	Execution timed out	2098 ms	673640 KB	Time limit exceeded
29	Execution timed out	2086 ms	692964 KB	Time limit exceeded
30	Execution timed out	2115 ms	723468 KB	Time limit exceeded
31	Execution timed out	2074 ms	749320 KB	Time limit exceeded
32	Execution timed out	2081 ms	636392 KB	Time limit exceeded