Submission #36545

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

tracks

/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#pragma GCC optimize("O3")
#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];
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", 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	113 ms	87512 KB	Output is correct
2	Correct	19 ms	82100 KB	Output is correct
3	Correct	16 ms	82100 KB	Output is correct
4	Correct	46 ms	83188 KB	Output is correct
5	Correct	39 ms	82496 KB	Output is correct
6	Correct	16 ms	82100 KB	Output is correct
7	Correct	16 ms	82100 KB	Output is correct
8	Correct	26 ms	82244 KB	Output is correct
9	Correct	29 ms	82100 KB	Output is correct
10	Correct	39 ms	82628 KB	Output is correct
11	Correct	26 ms	82368 KB	Output is correct
12	Correct	59 ms	83968 KB	Output is correct
13	Correct	29 ms	82496 KB	Output is correct
14	Correct	33 ms	82496 KB	Output is correct
15	Correct	103 ms	86060 KB	Output is correct
16	Correct	129 ms	87512 KB	Output is correct
17	Correct	76 ms	84216 KB	Output is correct
18	Correct	53 ms	83188 KB	Output is correct

Subtask #2

28.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	82232 KB	Output is correct
2	Correct	329 ms	95324 KB	Output is correct
3	Incorrect	1919 ms	90680 KB	Output isn't correct
4	Incorrect	529 ms	87512 KB	Output isn't correct
5	Incorrect	1226 ms	113384 KB	Output isn't correct
6	Execution timed out	2000 ms	98508 KB	Execution timed out
7	Correct	33 ms	82232 KB	Output is correct
8	Correct	33 ms	82232 KB	Output is correct
9	Correct	33 ms	82628 KB	Output is correct
10	Correct	19 ms	82232 KB	Output is correct
11	Correct	26 ms	82232 KB	Output is correct
12	Correct	33 ms	82496 KB	Output is correct
13	Correct	359 ms	95324 KB	Output is correct
14	Correct	219 ms	89756 KB	Output is correct
15	Correct	189 ms	86588 KB	Output is correct
16	Correct	166 ms	89496 KB	Output is correct
17	Incorrect	633 ms	98336 KB	Output isn't correct
18	Incorrect	646 ms	90680 KB	Output isn't correct
19	Incorrect	583 ms	87512 KB	Output isn't correct
20	Incorrect	439 ms	91604 KB	Output isn't correct
21	Incorrect	1149 ms	91100 KB	Output isn't correct
22	Incorrect	1273 ms	113384 KB	Output isn't correct
23	Incorrect	1196 ms	99024 KB	Output isn't correct
24	Incorrect	1119 ms	92264 KB	Output isn't correct
25	Execution timed out	2000 ms	90944 KB	Execution timed out
26	Correct	1466 ms	82100 KB	Output is correct
27	Execution timed out	2000 ms	83048 KB	Execution timed out
28	Execution timed out	2000 ms	98508 KB	Execution timed out
29	Execution timed out	2000 ms	94392 KB	Execution timed out
30	Execution timed out	2000 ms	95752 KB	Execution timed out
31	Incorrect	1949 ms	128584 KB	Output isn't correct
32	Execution timed out	2000 ms	83172 KB	Execution timed out