Submission #133973

#	Time	Username	Problem	Language	Result	Execution time	Memory
133973		Lawliet	Tracks in the Snow (BOI13_tracks)	C++14	86.88 / 100	2164 ms	1048576 KiB

tracks

#include <bits/stdc++.h>

#define MAX 4010

using namespace std;
typedef pair<int,int> pii;

int dx[] = {0 , 0 , 1 , -1};
int dy[] = {1 , -1 , 0 , 0};

int n, m;
int curNode;

int node[MAX][MAX];
int dist[MAX*MAX];

bool marc[MAX][MAX];
bool marcBFS[MAX*MAX];

pii cell[MAX*MAX];

char v[MAX][MAX];

//vector<int> dist;

//vector<bool> marcBFS;

//vector<pii> cell;

queue<int> q;

bool check(int i, int j)
{
	if(i <= 0 || j <= 0) return false;
	if(i > n || j > m) return false;

	return true;
}

void DFS(int i, int j)//ESTOU PEGANDO TODOS COM V
{
	marc[i][j] = true;

	for(int g = 0 ; g < 4 ; g++)
	{
		int ni = i + dx[g];
		int nj = j + dy[g];

		if(!check(ni , nj)) continue;

		if(marc[ni][nj]) continue;
		if(v[ni][nj] != v[i][j]) continue;

		node[ni][nj] = node[i][j];

		DFS(ni , nj);
	}
}

void DFSMake(int i, int j)
{
	marc[i][j] = true;

	for(int g = 0 ; g < 4 ; g++)
	{
		int ni = i + dx[g];
		int nj = j + dy[g];

		//printf("%d %d %d %d\n",i,j,ni,nj);

		if(!check(ni , nj)) continue;

		//printf("i = %d   %d %d %d\n",i,j,ni,nj);

		if(marc[ni][nj]) continue;

		//printf("i = %d  j = %d  ni = %d  nj = %d\n",i,j,ni,nj);

		if(v[ni][nj] == '.') continue;

		if(v[ni][nj] != v[i][j] && !marcBFS[ node[ni][nj] ])
		{
			if(!marcBFS[ node[ni][nj] ])
			{
				q.push( node[ni][nj] );

				marcBFS[ node[ni][nj] ] = true;
				dist[ node[ni][nj] ] = dist[ node[i][j] ] + 1;

			}
			//printf("i = %d  j = %d      %d %d\n",i,j,ni,nj);

			continue;
		}

		if(v[ni][nj] != v[i][j]) continue;

		DFSMake(ni , nj);
	}
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int g = 1 ; g <= n ; g++)
		for(int h = 1 ; h <= m ; h++)
			scanf(" %c",&v[g][h]);

	for(int g = 1 ; g <= n ; g++)
	{
		for(int h = 1 ; h <= m ; h++)
		{
			if(marc[g][h]) continue;
			if(v[g][h] == '.') continue;

			node[g][h] = curNode++;//CURNODE N EXISTE

			//printf("g = %d  h = %d    %d\n",g,h,curNode - 1) ;

			//dist.push_back( 0 );

			cell[curNode - 1] = {g , h};
			//cell.push_back({g , h});
			//marcBFS.push_back(false);

			DFS(g , h);
		}
	}

	memset(marc , false , sizeof(marc));

	marcBFS[0] = true;
	q.push(0);

	while( !q.empty() )
	{
		int cur = q.front(); q.pop();

		int i = cell[cur].first;
		int j = cell[cur].second;

		DFSMake(i , j);
	}

	int ans = 0;

	for(int g = 0 ; g < curNode ; g++)
		ans = max(ans , dist[g]);

	printf("%d\n",ans + 1);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
tracks.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&v[g][h]);
    ~~~~~^~~~~~~~~~~~~~~~

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