oj.uz

답안 #36546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36546 2017-12-10T12:44:54 Z ToMoClone Tracks in the Snow (BOI13_tracks) C++14
60.625 / 100
 2000 ms 237992 KB 
/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#pragma GCC optimize("Ofast")
#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];
map<pair<int, int>, int> edge;
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));
				if(edge.count(make_pair(u, v))) continue;
				child[u].push_back(v), child[v].push_back(u), edge[{u, v}] = 1;
			}

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

	for(int i = 1; i < N; ++i) l[i] = N;
	l[root(1)] = 0;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int v:child[u])
			if(l[v] > l[u] + 1){
				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:46: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:49: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 203 ms 90680 KB Output is correct
2 Correct 23 ms 82100 KB Output is correct
3 Correct 23 ms 82232 KB Output is correct
4 Correct 46 ms 82628 KB Output is correct
5 Correct 36 ms 83552 KB Output is correct
6 Correct 16 ms 82100 KB Output is correct
7 Correct 29 ms 82232 KB Output is correct
8 Correct 29 ms 82100 KB Output is correct
9 Correct 26 ms 82232 KB Output is correct
10 Correct 43 ms 83552 KB Output is correct
11 Correct 29 ms 82232 KB Output is correct
12 Correct 69 ms 85268 KB Output is correct
13 Correct 49 ms 83552 KB Output is correct
14 Correct 36 ms 83552 KB Output is correct
15 Correct 143 ms 89888 KB Output is correct
16 Correct 199 ms 90680 KB Output is correct
17 Correct 116 ms 89228 KB Output is correct
18 Correct 56 ms 82628 KB Output is correct

Subtask #2
30.625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 82892 KB Output is correct
2 Correct 583 ms 118808 KB Output is correct
3 Execution timed out 2000 ms 112856 KB Execution timed out
4 Incorrect 656 ms 106128 KB Output isn't correct
5 Execution timed out 2000 ms 237992 KB Execution timed out
6 Execution timed out 2000 ms 96892 KB Execution timed out
7 Correct 29 ms 82760 KB Output is correct
8 Correct 33 ms 82892 KB Output is correct
9 Correct 36 ms 83420 KB Output is correct
10 Correct 23 ms 82496 KB Output is correct
11 Correct 23 ms 82496 KB Output is correct
12 Correct 46 ms 83816 KB Output is correct
13 Correct 536 ms 118808 KB Output is correct
14 Correct 326 ms 103484 KB Output is correct
15 Correct 306 ms 104408 KB Output is correct
16 Correct 313 ms 99788 KB Output is correct
17 Incorrect 989 ms 128564 KB Output isn't correct
18 Incorrect 1012 ms 125132 KB Output isn't correct
19 Incorrect 646 ms 106128 KB Output isn't correct
20 Incorrect 666 ms 114836 KB Output isn't correct
21 Incorrect 1293 ms 114044 KB Output isn't correct
22 Execution timed out 2000 ms 237992 KB Execution timed out
23 Incorrect 1403 ms 130016 KB Output isn't correct
24 Incorrect 1363 ms 132920 KB Output isn't correct
25 Execution timed out 2000 ms 126056 KB Execution timed out
26 Correct 1486 ms 82100 KB Output is correct
27 Correct 1939 ms 82364 KB Output is correct
28 Execution timed out 2000 ms 96892 KB Execution timed out
29 Execution timed out 2000 ms 89316 KB Execution timed out
30 Execution timed out 2000 ms 89628 KB Execution timed out
31 Execution timed out 2000 ms 151724 KB Execution timed out
32 Execution timed out 2000 ms 83552 KB Execution timed out