oj.uz

Submission #69482

# Submission time Handle Problem Language Result Execution time Memory
69482 2018-08-21T03:03:03 Z MatheusLealV Tracks in the Snow (BOI13_tracks) C++17
75.9375 / 100
 2000 ms 1049600 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];

char mat[N][N], T;

vector<int> grafo[N*N];

void dfs(int x, int y, int &p)
{
	//cout<<"DFS "<<x<<" "<<y<<"\n";
	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;

		//cout<<"VIZ "<<x<<" "<<y<<" "<<a<<" "<<b<<"\n";

		dfs(a, b, p);
	}
}

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;
			//cout<<"INI "<<i<<" "<<j<<"\n";
			dfs(i, j, id[i][j]);	
			//cout<<"FIM "<<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 = pai[id[a][b]], v = pai[id[i][j]];

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

	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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 389676 KB Output is correct
2 Correct 340 ms 389676 KB Output is correct
3 Correct 322 ms 389676 KB Output is correct
4 Correct 367 ms 389676 KB Output is correct
5 Correct 335 ms 389676 KB Output is correct
6 Correct 355 ms 389676 KB Output is correct
7 Correct 321 ms 389676 KB Output is correct
8 Correct 378 ms 389676 KB Output is correct
9 Correct 327 ms 389676 KB Output is correct
10 Correct 422 ms 389676 KB Output is correct
11 Correct 337 ms 389676 KB Output is correct
12 Correct 395 ms 389676 KB Output is correct
13 Correct 371 ms 389676 KB Output is correct
14 Correct 367 ms 389676 KB Output is correct
15 Correct 398 ms 390104 KB Output is correct
16 Correct 404 ms 390904 KB Output is correct
17 Correct 395 ms 390904 KB Output is correct
18 Correct 352 ms 390904 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 425424 KB Output is correct
2 Correct 579 ms 425528 KB Output is correct
3 Execution timed out 2107 ms 600388 KB Time limit exceeded
4 Correct 885 ms 600388 KB Output is correct
5 Execution timed out 2048 ms 685836 KB Time limit exceeded
6 Execution timed out 2095 ms 685836 KB Time limit exceeded
7 Correct 362 ms 685836 KB Output is correct
8 Correct 366 ms 685836 KB Output is correct
9 Correct 329 ms 685836 KB Output is correct
10 Correct 316 ms 685836 KB Output is correct
11 Correct 409 ms 685836 KB Output is correct
12 Correct 391 ms 685836 KB Output is correct
13 Correct 621 ms 685836 KB Output is correct
14 Correct 470 ms 685836 KB Output is correct
15 Correct 521 ms 685836 KB Output is correct
16 Correct 509 ms 685836 KB Output is correct
17 Correct 1008 ms 685836 KB Output is correct
18 Correct 1044 ms 685836 KB Output is correct
19 Correct 817 ms 685836 KB Output is correct
20 Correct 754 ms 685836 KB Output is correct
21 Correct 1401 ms 685836 KB Output is correct
22 Correct 1979 ms 685924 KB Output is correct
23 Correct 1602 ms 685924 KB Output is correct
24 Correct 1406 ms 685924 KB Output is correct
25 Execution timed out 2141 ms 685924 KB Time limit exceeded
26 Execution timed out 2138 ms 1049600 KB Time limit exceeded
27 Execution timed out 2110 ms 1049600 KB Time limit exceeded
28 Execution timed out 2130 ms 1049600 KB Time limit exceeded
29 Execution timed out 2101 ms 1049600 KB Time limit exceeded
30 Execution timed out 2116 ms 1049600 KB Time limit exceeded
31 Execution timed out 2090 ms 1049600 KB Time limit exceeded
32 Execution timed out 2120 ms 1049600 KB Time limit exceeded