Submission #111802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111802	2019-05-16T08:07:01 Z	anayk	Tracks in the Snow (BOI13_tracks)	C++14	80.3125 / 100	2000 ms	958392 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::ios::sync_with_stdio(false);
	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	464 ms	431096 KB	Output is correct
2	Correct	401 ms	416412 KB	Output is correct
3	Correct	375 ms	416564 KB	Output is correct
4	Correct	429 ms	426748 KB	Output is correct
5	Correct	412 ms	418880 KB	Output is correct
6	Correct	368 ms	416372 KB	Output is correct
7	Correct	350 ms	416632 KB	Output is correct
8	Correct	380 ms	416856 KB	Output is correct
9	Correct	352 ms	416740 KB	Output is correct
10	Correct	358 ms	418936 KB	Output is correct
11	Correct	405 ms	419192 KB	Output is correct
12	Correct	381 ms	422008 KB	Output is correct
13	Correct	397 ms	418680 KB	Output is correct
14	Correct	401 ms	418876 KB	Output is correct
15	Correct	429 ms	428516 KB	Output is correct
16	Correct	438 ms	431224 KB	Output is correct
17	Correct	421 ms	424456 KB	Output is correct
18	Correct	434 ms	426744 KB	Output is correct

Subtask #2

50.3125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	419 ms	432444 KB	Output is correct
2	Correct	613 ms	462304 KB	Output is correct
3	Correct	1447 ms	674296 KB	Output is correct
4	Correct	723 ms	474160 KB	Output is correct
5	Correct	1166 ms	628060 KB	Output is correct
6	Execution timed out	2110 ms	817400 KB	Time limit exceeded
7	Correct	369 ms	433064 KB	Output is correct
8	Correct	376 ms	432380 KB	Output is correct
9	Correct	405 ms	418044 KB	Output is correct
10	Correct	414 ms	416760 KB	Output is correct
11	Correct	445 ms	432636 KB	Output is correct
12	Correct	361 ms	417400 KB	Output is correct
13	Correct	657 ms	462028 KB	Output is correct
14	Correct	553 ms	443776 KB	Output is correct
15	Correct	470 ms	437240 KB	Output is correct
16	Correct	475 ms	438904 KB	Output is correct
17	Correct	998 ms	526332 KB	Output is correct
18	Correct	966 ms	490616 KB	Output is correct
19	Correct	696 ms	473848 KB	Output is correct
20	Correct	675 ms	485352 KB	Output is correct
21	Correct	1104 ms	584824 KB	Output is correct
22	Correct	1155 ms	628216 KB	Output is correct
23	Correct	1334 ms	621432 KB	Output is correct
24	Correct	940 ms	578680 KB	Output is correct
25	Execution timed out	2072 ms	674296 KB	Time limit exceeded
26	Execution timed out	2102 ms	953316 KB	Time limit exceeded
27	Execution timed out	2112 ms	958392 KB	Time limit exceeded
28	Execution timed out	2108 ms	840788 KB	Time limit exceeded
29	Execution timed out	2085 ms	850788 KB	Time limit exceeded
30	Execution timed out	2112 ms	809284 KB	Time limit exceeded
31	Execution timed out	2132 ms	849144 KB	Time limit exceeded
32	Execution timed out	2111 ms	947684 KB	Time limit exceeded