oj.uz

Submission #69483

# Submission time Handle Problem Language Result Execution time Memory
69483 2018-08-21T03:04:11 Z MatheusLealV Tracks in the Snow (BOI13_tracks) C++17
80.3125 / 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 416 ms 389624 KB Output is correct
2 Correct 321 ms 389624 KB Output is correct
3 Correct 326 ms 389624 KB Output is correct
4 Correct 334 ms 389624 KB Output is correct
5 Correct 329 ms 389624 KB Output is correct
6 Correct 324 ms 389624 KB Output is correct
7 Correct 332 ms 389624 KB Output is correct
8 Correct 356 ms 389624 KB Output is correct
9 Correct 383 ms 389624 KB Output is correct
10 Correct 333 ms 389624 KB Output is correct
11 Correct 333 ms 389624 KB Output is correct
12 Correct 350 ms 389624 KB Output is correct
13 Correct 385 ms 389624 KB Output is correct
14 Correct 334 ms 389624 KB Output is correct
15 Correct 389 ms 390104 KB Output is correct
16 Correct 383 ms 390984 KB Output is correct
17 Correct 410 ms 390984 KB Output is correct
18 Correct 342 ms 390984 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 425468 KB Output is correct
2 Correct 607 ms 425636 KB Output is correct
3 Correct 1396 ms 663200 KB Output is correct
4 Correct 714 ms 663200 KB Output is correct
5 Correct 1607 ms 688888 KB Output is correct
6 Execution timed out 2117 ms 688888 KB Time limit exceeded
7 Correct 357 ms 688888 KB Output is correct
8 Correct 403 ms 688888 KB Output is correct
9 Correct 332 ms 688888 KB Output is correct
10 Correct 340 ms 688888 KB Output is correct
11 Correct 366 ms 688888 KB Output is correct
12 Correct 315 ms 688888 KB Output is correct
13 Correct 488 ms 688888 KB Output is correct
14 Correct 420 ms 688888 KB Output is correct
15 Correct 432 ms 688888 KB Output is correct
16 Correct 389 ms 688888 KB Output is correct
17 Correct 772 ms 688888 KB Output is correct
18 Correct 813 ms 688888 KB Output is correct
19 Correct 707 ms 688888 KB Output is correct
20 Correct 671 ms 688888 KB Output is correct
21 Correct 1079 ms 688888 KB Output is correct
22 Correct 1483 ms 688888 KB Output is correct
23 Correct 1177 ms 688888 KB Output is correct
24 Correct 977 ms 688888 KB Output is correct
25 Execution timed out 2105 ms 733996 KB Time limit exceeded
26 Execution timed out 2072 ms 1049600 KB Time limit exceeded
27 Runtime error 1610 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
28 Execution timed out 2099 ms 1049600 KB Time limit exceeded
29 Execution timed out 2092 ms 1049600 KB Time limit exceeded
30 Runtime error 1963 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
31 Execution timed out 2095 ms 1049600 KB Time limit exceeded
32 Runtime error 1520 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.