Submission #36542

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36542	2017-12-10T12:19:19 Z	ToMoClone	Tracks in the Snow (BOI13_tracks)	C++14	58.4375 / 100	2000 ms	178988 KB

tracks

/*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);
                              ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	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

Subtask #2

28.4375 / 70.0

#	Verdict	Execution time	Memory	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