Submission #69480

#	Time	Username	Problem	Language	Result	Execution time	Memory
69480		MatheusLealV	Tracks in the Snow (BOI13_tracks)	C++17	86.88 / 100	2128 ms	860220 KiB

tracks

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

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

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

inline int Find(int x)
{
	if(pai[x] == x) return x;

	return pai[x] = Find(pai[x]);
}

inline void join(int a, int b)
{
	a = Find(a), b = Find(b);

	if(a == b) return;

	if(peso[a] > peso[b]) pai[b] = a;

	else if(peso[a] < peso[b]) pai[a] = b;

	else pai[a] = b, peso[b] ++;
}

char mat[N][N], T;

vector<int> grafo[N*N];

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];

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			id[i][j] = ++cnt;

	for(int i = 1; i <= cnt; i++) pai[i] = i;

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

			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 or mat[a][b] != mat[i][j]) continue;

				join(id[a][b], id[i][j]);

				//cout<<"JOIN "<<a<<" "<<b<<" "<<i<<" "<<j<<"\n";	
			}
		}
	}

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

			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 = Find(id[a][b]), v = Find(id[i][j]);

					grafo[u].push_back(v);

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

	queue<int> fila;

	memset(dist, 0x3f3f3f3f, sizeof dist);

	dist[Find(id[1][1])] = 1;

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

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

		fila.pop();

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

				fila.push(v);
			}
		}
	}

	/*for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cout<<Find(id[i][j])<<" ";
		}
		cout<<"\n";
	}*/

	for(int i = 1; i <= cnt; i++)
	{
		//cout<<i<<" "<<dist[i]<<"\n";

		if(dist[i] != 0x3f3f3f3f) ans = max(ans, dist[i]);
	}

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

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