Submission #111801

#	Time	Username	Problem	Language	Result	Execution time	Memory
111801		anayk	Tracks in the Snow (BOI13_tracks)	C++14	78.13 / 100	2131 ms	749320 KiB

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 / 30
• Subtask 2: 48.125 / 70