Submission #36543

#	Time	Username	Problem	Language	Result	Execution time	Memory
36543		ToMoClone	Tracks in the Snow (BOI13_tracks)	C++14	58.44 / 100	2000 ms	185740 KiB

tracks

/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#include <cstring>
#include <stdio.h>
#include <queue>
#include <set>
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 1666661;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int Arr[N], Size[N], visit[N], l[N], n, m, ans = 1;
char Type[N];
set<int> child[N];

int get(int x, int y){
	int k = (x - 1) * (m + 1) + y;
	return (0 <= k && k < N) ? k : 0;
}

void init(){
	for(int i = 0; i < N; ++i)
		Arr[i] = i, Size[i] = 1;
}

int root(int a){
	if(a == Arr[a]) return a;
	return Arr[a] = root(Arr[a]);
}

void Union(int a, int b){
	a = root(a), b = root(b);
	if(a == b) return;
	if(Size[a] < Size[b]) swap(a, b);
	Arr[b] = a, Size[a] += Size[b];
}

int main(){
	memset(visit, -1, sizeof visit);
	init();

	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j){
			char ch; scanf(" %c", &ch);
			if(ch == '.') continue;
			Type[get(i, j)] = ch;
			visit[get(i, j)] = 0;
		}

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			if(visit[get(i, j)] != -1) for(int dir = 0; dir < 4; ++dir){
				int newx = i + dx[dir], newy = j + dy[dir];
				if(visit[get(newx, newy)] || Type[get(i, j)] != Type[get(newx, newy)]) continue;
				Union(get(i, j), get(newx, newy));
			}

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			if(visit[get(i, j)] != -1) for(int dir = 0; dir < 4; ++dir){
				int newx = i + dx[dir], newy = j + dy[dir];
				if(visit[get(newx, newy)] || Type[get(i, j)] == Type[get(newx, newy)]) continue;
				int u = root(get(newx, newy)), v = root(get(i, j));
				child[u].insert(v), child[v].insert(u);
			}

	queue<int> q;
	q.push(root(1));
	memset(visit, 0, sizeof visit);
	visit[root(1)] = 1;

	while(q.size()){
		int u = q.front(); q.pop();
		for(int v:child[u])
			if(!visit[v]){
				l[v] = l[u] + 1, ans = max(ans, l[v] + 1);
				visit[v] = 1, q.push(v);
			}
	}

	// printf("%d\n", root(1));
	// for(int i = 1; i <= n; ++i){
	// 	for(int j = 1; j <= m; ++j)
	// 		printf("%d ", root(get(i, j)));
	// 	puts("");
	// }
	printf("%d\n", ans);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:48:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
tracks.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    char ch; scanf(" %c", &ch);
                              ^

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