oj.uz

답안 #36547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36547 2017-12-10T12:46:16 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>, bool> 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 193 ms 90680 KB Output is correct
2 Correct 19 ms 82100 KB Output is correct
3 Correct 23 ms 82232 KB Output is correct
4 Correct 56 ms 82628 KB Output is correct
5 Correct 46 ms 83552 KB Output is correct
6 Correct 19 ms 82100 KB Output is correct
7 Correct 13 ms 82232 KB Output is correct
8 Correct 23 ms 82100 KB Output is correct
9 Correct 36 ms 82232 KB Output is correct
10 Correct 36 ms 83552 KB Output is correct
11 Correct 33 ms 82232 KB Output is correct
12 Correct 69 ms 85268 KB Output is correct
13 Correct 33 ms 83552 KB Output is correct
14 Correct 43 ms 83552 KB Output is correct
15 Correct 159 ms 89888 KB Output is correct
16 Correct 186 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 26 ms 82892 KB Output is correct
2 Correct 519 ms 118808 KB Output is correct
3 Execution timed out 2000 ms 112856 KB Execution timed out
4 Incorrect 663 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 19 ms 82760 KB Output is correct
8 Correct 29 ms 82892 KB Output is correct
9 Correct 46 ms 83420 KB Output is correct
10 Correct 19 ms 82496 KB Output is correct
11 Correct 29 ms 82496 KB Output is correct
12 Correct 29 ms 83816 KB Output is correct
13 Correct 603 ms 118808 KB Output is correct
14 Correct 326 ms 103484 KB Output is correct
15 Correct 379 ms 104408 KB Output is correct
16 Correct 289 ms 99788 KB Output is correct
17 Incorrect 943 ms 128564 KB Output isn't correct
18 Incorrect 906 ms 125132 KB Output isn't correct
19 Incorrect 659 ms 106128 KB Output isn't correct
20 Incorrect 629 ms 114836 KB Output isn't correct
21 Incorrect 1289 ms 114044 KB Output isn't correct
22 Execution timed out 2000 ms 237992 KB Execution timed out
23 Incorrect 1356 ms 130016 KB Output isn't correct
24 Incorrect 1293 ms 132920 KB Output isn't correct
25 Execution timed out 2000 ms 126056 KB Execution timed out
26 Correct 1446 ms 82100 KB Output is correct
27 Correct 1879 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