oj.uz

Submission #69480

# Submission time Handle Problem Language Result Execution time Memory
69480 2018-08-21T02:46:36 Z MatheusLealV Tracks in the Snow (BOI13_tracks) C++17
86.875 / 100
 2000 ms 860220 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 451896 KB Output is correct
2 Correct 412 ms 451896 KB Output is correct
3 Correct 432 ms 451896 KB Output is correct
4 Correct 418 ms 451896 KB Output is correct
5 Correct 368 ms 451896 KB Output is correct
6 Correct 398 ms 451896 KB Output is correct
7 Correct 367 ms 451896 KB Output is correct
8 Correct 363 ms 451896 KB Output is correct
9 Correct 424 ms 451896 KB Output is correct
10 Correct 378 ms 451896 KB Output is correct
11 Correct 420 ms 451896 KB Output is correct
12 Correct 450 ms 451896 KB Output is correct
13 Correct 385 ms 451896 KB Output is correct
14 Correct 387 ms 451896 KB Output is correct
15 Correct 454 ms 451896 KB Output is correct
16 Correct 506 ms 453224 KB Output is correct
17 Correct 484 ms 453224 KB Output is correct
18 Correct 455 ms 453224 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 472668 KB Output is correct
2 Correct 651 ms 484304 KB Output is correct
3 Correct 1780 ms 699704 KB Output is correct
4 Correct 775 ms 699704 KB Output is correct
5 Correct 1600 ms 704344 KB Output is correct
6 Execution timed out 2128 ms 704416 KB Time limit exceeded
7 Correct 455 ms 704416 KB Output is correct
8 Correct 465 ms 704416 KB Output is correct
9 Correct 386 ms 704416 KB Output is correct
10 Correct 365 ms 704416 KB Output is correct
11 Correct 381 ms 704416 KB Output is correct
12 Correct 366 ms 704416 KB Output is correct
13 Correct 589 ms 704416 KB Output is correct
14 Correct 542 ms 704416 KB Output is correct
15 Correct 516 ms 704416 KB Output is correct
16 Correct 611 ms 704416 KB Output is correct
17 Correct 1030 ms 704416 KB Output is correct
18 Correct 917 ms 704416 KB Output is correct
19 Correct 721 ms 704416 KB Output is correct
20 Correct 666 ms 704416 KB Output is correct
21 Correct 1079 ms 704416 KB Output is correct
22 Correct 1582 ms 753312 KB Output is correct
23 Correct 1467 ms 753312 KB Output is correct
24 Correct 1268 ms 753312 KB Output is correct
25 Execution timed out 2111 ms 802344 KB Time limit exceeded
26 Correct 1196 ms 802344 KB Output is correct
27 Correct 1590 ms 802344 KB Output is correct
28 Execution timed out 2101 ms 802344 KB Time limit exceeded
29 Execution timed out 2111 ms 822016 KB Time limit exceeded
30 Execution timed out 2093 ms 860220 KB Time limit exceeded
31 Execution timed out 2115 ms 860220 KB Time limit exceeded
32 Correct 1570 ms 860220 KB Output is correct