답안 #36542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36542 2017-12-10T12:19:19 Z ToMoClone Tracks in the Snow (BOI13_tracks) C++14
58.4375 / 100
2000 ms 178988 KB
/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#include <cstring>
#include <stdio.h>
#include <queue>
#include <set>
using namespace std;

const int N = 1606061;
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

tracks.cpp: In function 'int main()':
tracks.cpp:47: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:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    char ch; scanf(" %c", &ch);
                              ^
# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 109028 KB Output is correct
2 Correct 26 ms 103880 KB Output is correct
3 Correct 23 ms 103880 KB Output is correct
4 Correct 63 ms 104144 KB Output is correct
5 Correct 39 ms 104804 KB Output is correct
6 Correct 23 ms 103880 KB Output is correct
7 Correct 26 ms 103880 KB Output is correct
8 Correct 26 ms 103880 KB Output is correct
9 Correct 33 ms 104012 KB Output is correct
10 Correct 26 ms 104804 KB Output is correct
11 Correct 23 ms 104012 KB Output is correct
12 Correct 56 ms 105728 KB Output is correct
13 Correct 39 ms 104804 KB Output is correct
14 Correct 33 ms 104804 KB Output is correct
15 Correct 89 ms 108500 KB Output is correct
16 Correct 123 ms 109028 KB Output is correct
17 Correct 73 ms 108236 KB Output is correct
18 Correct 53 ms 104144 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 104408 KB Output is correct
2 Correct 343 ms 125924 KB Output is correct
3 Execution timed out 2000 ms 118268 KB Execution timed out
4 Incorrect 503 ms 114572 KB Output isn't correct
5 Incorrect 1366 ms 178988 KB Output isn't correct
6 Execution timed out 2000 ms 110876 KB Execution timed out
7 Correct 33 ms 104276 KB Output is correct
8 Correct 36 ms 104408 KB Output is correct
9 Correct 36 ms 104672 KB Output is correct
10 Correct 26 ms 104144 KB Output is correct
11 Correct 33 ms 104144 KB Output is correct
12 Correct 33 ms 104936 KB Output is correct
13 Correct 359 ms 125924 KB Output is correct
14 Correct 239 ms 116684 KB Output is correct
15 Correct 243 ms 117212 KB Output is correct
16 Correct 196 ms 114440 KB Output is correct
17 Incorrect 649 ms 126188 KB Output isn't correct
18 Incorrect 663 ms 124604 KB Output isn't correct
19 Incorrect 539 ms 114572 KB Output isn't correct
20 Incorrect 429 ms 119720 KB Output isn't correct
21 Incorrect 1259 ms 119588 KB Output isn't correct
22 Incorrect 1296 ms 178988 KB Output isn't correct
23 Incorrect 1083 ms 126584 KB Output isn't correct
24 Incorrect 1139 ms 128168 KB Output isn't correct
25 Execution timed out 2000 ms 125000 KB Execution timed out
26 Correct 1633 ms 103880 KB Output is correct
27 Execution timed out 2000 ms 104012 KB Execution timed out
28 Execution timed out 2000 ms 110876 KB Execution timed out
29 Execution timed out 2000 ms 107312 KB Execution timed out
30 Execution timed out 2000 ms 107444 KB Execution timed out
31 Incorrect 1809 ms 137672 KB Output isn't correct
32 Execution timed out 2000 ms 104408 KB Execution timed out