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
#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;
}
# 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
# 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