Submission #69488

#	Time	Username	Problem	Language	Result	Execution time	Memory
69488		MatheusLealV	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	2114 ms	631816 KiB

tracks

#include <bits/stdc++.h>
#define N 4001
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, ans, cnt, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int id[N][N], pai[N*N], dist[N*N];

bool ok[N][N], Fill[N*N];

char mat[N][N], T;

vector<int> grafo[N*N];

inline void bfs(int x, int y, int &p)
{
	queue< pii > fila;

	fila.push({x, y});

	while(!fila.empty())
	{
		int x = fila.front().f, y = fila.front().s;

		fila.pop();

		ok[x][y] = 1;

		pai[id[x][y]] = p;

		for(int pp = 0; pp < 4; pp++)
		{
			int a = x + dx[pp], b = y + dy[pp];

			if(!a or !b or a > n or b > m or mat[a][b] != mat[x][y] or ok[a][b]) continue;

			ok[a][b] = 1;

			fila.push({a, b});
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
		 	cin>>mat[i][j];

		 	id[i][j] = ++cnt;

		 	pai[id[i][j]] = id[i][j];
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(mat[i][j] == '.' or ok[i][j]) continue;

			bfs(i, j, id[i][j]);	
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(mat[i][j] == '.') continue;

			if(Fill[pai[id[i][j]]]) continue;

			Fill[pai[id[i][j]]] = 1;

			for(int p = 0; p < 4; p++)
			{
				int a = i + dx[p], b = j + dy[p];

				if(!a or !b or a > n or b > m) continue;

				if(mat[a][b] != mat[i][j] and mat[a][b] != '.')
				{
					int u = pai[id[a][b]], v = pai[id[i][j]];

					grafo[v].push_back(u);
				}
			}
		}
	}

	queue<int> fila;

	dist[pai[id[1][1]]] = 1;

	fila.push(pai[id[1][1]]);

	while(!fila.empty())
	{
		int x = fila.front();

		ans = max(ans, dist[x]);

		fila.pop();

		for(auto v: grafo[x])
		{
			if(dist[v] == 0)
			{
				dist[v] = dist[x] + 1;

				fila.push(v);
			}
		}
	}

	cout<<ans<<"\n";
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70