Submission #36543

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

tracks

/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#include <cstring>
#include <stdio.h>
#include <queue>
#include <set>
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 1666661;
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:48: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:51: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	139 ms	112876 KB	Output is correct
2	Correct	29 ms	107728 KB	Output is correct
3	Correct	33 ms	107728 KB	Output is correct
4	Correct	76 ms	107992 KB	Output is correct
5	Correct	43 ms	108652 KB	Output is correct
6	Correct	23 ms	107728 KB	Output is correct
7	Correct	23 ms	107728 KB	Output is correct
8	Correct	23 ms	107728 KB	Output is correct
9	Correct	36 ms	107860 KB	Output is correct
10	Correct	36 ms	108652 KB	Output is correct
11	Correct	26 ms	107860 KB	Output is correct
12	Correct	56 ms	109576 KB	Output is correct
13	Correct	46 ms	108652 KB	Output is correct
14	Correct	36 ms	108652 KB	Output is correct
15	Correct	109 ms	112348 KB	Output is correct
16	Correct	139 ms	112876 KB	Output is correct
17	Correct	103 ms	112084 KB	Output is correct
18	Correct	53 ms	107992 KB	Output is correct

Subtask #2

28.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	108256 KB	Output is correct
2	Correct	346 ms	129772 KB	Output is correct
3	Incorrect	1936 ms	122776 KB	Output isn't correct
4	Incorrect	559 ms	118948 KB	Output isn't correct
5	Incorrect	1176 ms	185740 KB	Output isn't correct
6	Execution timed out	2000 ms	114988 KB	Execution timed out
7	Correct	36 ms	108124 KB	Output is correct
8	Correct	36 ms	108256 KB	Output is correct
9	Correct	29 ms	108520 KB	Output is correct
10	Correct	29 ms	107992 KB	Output is correct
11	Correct	23 ms	107992 KB	Output is correct
12	Correct	29 ms	108784 KB	Output is correct
13	Correct	416 ms	129772 KB	Output is correct
14	Correct	206 ms	120532 KB	Output is correct
15	Correct	213 ms	121060 KB	Output is correct
16	Correct	173 ms	118288 KB	Output is correct
17	Incorrect	686 ms	130828 KB	Output isn't correct
18	Incorrect	666 ms	129244 KB	Output isn't correct
19	Incorrect	573 ms	118948 KB	Output isn't correct
20	Incorrect	463 ms	124228 KB	Output isn't correct
21	Incorrect	1149 ms	124096 KB	Output isn't correct
22	Incorrect	1249 ms	185740 KB	Output isn't correct
23	Incorrect	1143 ms	131356 KB	Output isn't correct
24	Incorrect	1159 ms	132940 KB	Output isn't correct
25	Execution timed out	2000 ms	129640 KB	Execution timed out
26	Correct	1499 ms	107728 KB	Output is correct
27	Execution timed out	2000 ms	107860 KB	Execution timed out
28	Execution timed out	2000 ms	114988 KB	Execution timed out
29	Execution timed out	2000 ms	111292 KB	Execution timed out
30	Incorrect	1869 ms	111424 KB	Output isn't correct
31	Incorrect	1833 ms	142840 KB	Output isn't correct
32	Incorrect	1989 ms	108256 KB	Output isn't correct