oj.uz

답안 #36545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36545 2017-12-10T12:30:26 Z ToMoClone Tracks in the Snow (BOI13_tracks) C++14
58.4375 / 100
 2000 ms 128584 KB 
/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

const int N = 2000005;
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];
vector<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)] == -1 || 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)] == -1 || Type[get(i, j)] == Type[get(newx, newy)]) continue;
				int u = root(get(newx, newy)), v = root(get(i, j));
				child[u].push_back(v), child[v].push_back(u);
			}

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

	while(q.size()){
		int u = q.front(); q.pop();
		sort(child[u].begin(), child[u].end());
		child[u].erase(unique(child[u].begin(), child[u].end()), child[u].end());

		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", ans);
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:45: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:48: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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 87512 KB Output is correct
2 Correct 19 ms 82100 KB Output is correct
3 Correct 16 ms 82100 KB Output is correct
4 Correct 46 ms 83188 KB Output is correct
5 Correct 39 ms 82496 KB Output is correct
6 Correct 16 ms 82100 KB Output is correct
7 Correct 16 ms 82100 KB Output is correct
8 Correct 26 ms 82244 KB Output is correct
9 Correct 29 ms 82100 KB Output is correct
10 Correct 39 ms 82628 KB Output is correct
11 Correct 26 ms 82368 KB Output is correct
12 Correct 59 ms 83968 KB Output is correct
13 Correct 29 ms 82496 KB Output is correct
14 Correct 33 ms 82496 KB Output is correct
15 Correct 103 ms 86060 KB Output is correct
16 Correct 129 ms 87512 KB Output is correct
17 Correct 76 ms 84216 KB Output is correct
18 Correct 53 ms 83188 KB Output is correct

Subtask #2
28.4375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 82232 KB Output is correct
2 Correct 329 ms 95324 KB Output is correct
3 Incorrect 1919 ms 90680 KB Output isn't correct
4 Incorrect 529 ms 87512 KB Output isn't correct
5 Incorrect 1226 ms 113384 KB Output isn't correct
6 Execution timed out 2000 ms 98508 KB Execution timed out
7 Correct 33 ms 82232 KB Output is correct
8 Correct 33 ms 82232 KB Output is correct
9 Correct 33 ms 82628 KB Output is correct
10 Correct 19 ms 82232 KB Output is correct
11 Correct 26 ms 82232 KB Output is correct
12 Correct 33 ms 82496 KB Output is correct
13 Correct 359 ms 95324 KB Output is correct
14 Correct 219 ms 89756 KB Output is correct
15 Correct 189 ms 86588 KB Output is correct
16 Correct 166 ms 89496 KB Output is correct
17 Incorrect 633 ms 98336 KB Output isn't correct
18 Incorrect 646 ms 90680 KB Output isn't correct
19 Incorrect 583 ms 87512 KB Output isn't correct
20 Incorrect 439 ms 91604 KB Output isn't correct
21 Incorrect 1149 ms 91100 KB Output isn't correct
22 Incorrect 1273 ms 113384 KB Output isn't correct
23 Incorrect 1196 ms 99024 KB Output isn't correct
24 Incorrect 1119 ms 92264 KB Output isn't correct
25 Execution timed out 2000 ms 90944 KB Execution timed out
26 Correct 1466 ms 82100 KB Output is correct
27 Execution timed out 2000 ms 83048 KB Execution timed out
28 Execution timed out 2000 ms 98508 KB Execution timed out
29 Execution timed out 2000 ms 94392 KB Execution timed out
30 Execution timed out 2000 ms 95752 KB Execution timed out
31 Incorrect 1949 ms 128584 KB Output isn't correct
32 Execution timed out 2000 ms 83172 KB Execution timed out