Submission #36547

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

tracks

/*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

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

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