Submission #36544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36544	2017-12-10T12:28:09 Z	ToMoClone	Tracks in the Snow (BOI13_tracks)	C++14	60.625 / 100	2000 ms	107588 KB

tracks

/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
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];
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", 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: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

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	74168 KB	Output is correct
2	Correct	16 ms	68756 KB	Output is correct
3	Correct	23 ms	68756 KB	Output is correct
4	Correct	39 ms	69844 KB	Output is correct
5	Correct	33 ms	69152 KB	Output is correct
6	Correct	19 ms	68756 KB	Output is correct
7	Correct	19 ms	68756 KB	Output is correct
8	Correct	19 ms	68900 KB	Output is correct
9	Correct	29 ms	68756 KB	Output is correct
10	Correct	29 ms	69284 KB	Output is correct
11	Correct	26 ms	69024 KB	Output is correct
12	Correct	46 ms	70624 KB	Output is correct
13	Correct	36 ms	69152 KB	Output is correct
14	Correct	29 ms	69152 KB	Output is correct
15	Correct	89 ms	72716 KB	Output is correct
16	Correct	103 ms	74168 KB	Output is correct
17	Correct	69 ms	70872 KB	Output is correct
18	Correct	59 ms	69844 KB	Output is correct

Subtask #2

30.625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	68888 KB	Output is correct
2	Correct	356 ms	81980 KB	Output is correct
3	Incorrect	1779 ms	75884 KB	Output isn't correct
4	Incorrect	463 ms	72980 KB	Output isn't correct
5	Incorrect	1113 ms	94760 KB	Output isn't correct
6	Incorrect	1936 ms	82964 KB	Output isn't correct
7	Correct	19 ms	68888 KB	Output is correct
8	Correct	29 ms	68888 KB	Output is correct
9	Correct	36 ms	69284 KB	Output is correct
10	Correct	13 ms	68888 KB	Output is correct
11	Correct	16 ms	68888 KB	Output is correct
12	Correct	19 ms	69152 KB	Output is correct
13	Correct	343 ms	81980 KB	Output is correct
14	Correct	189 ms	76412 KB	Output is correct
15	Correct	176 ms	73244 KB	Output is correct
16	Correct	169 ms	76152 KB	Output is correct
17	Incorrect	579 ms	82280 KB	Output isn't correct
18	Incorrect	633 ms	75884 KB	Output isn't correct
19	Incorrect	496 ms	72980 KB	Output isn't correct
20	Incorrect	416 ms	76808 KB	Output isn't correct
21	Incorrect	1096 ms	76544 KB	Output isn't correct
22	Incorrect	1083 ms	94760 KB	Output isn't correct
23	Incorrect	946 ms	82780 KB	Output isn't correct
24	Incorrect	1073 ms	77204 KB	Output isn't correct
25	Execution timed out	2000 ms	76156 KB	Execution timed out
26	Correct	1346 ms	68756 KB	Output is correct
27	Correct	1839 ms	69488 KB	Output is correct
28	Execution timed out	2000 ms	82964 KB	Execution timed out
29	Execution timed out	2000 ms	80708 KB	Execution timed out
30	Execution timed out	2000 ms	82052 KB	Execution timed out
31	Incorrect	1786 ms	107588 KB	Output isn't correct
32	Incorrect	1843 ms	69696 KB	Output isn't correct