Submission #36546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36546	2017-12-10T12:44:54 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>, int> 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	203 ms	90680 KB	Output is correct
2	Correct	23 ms	82100 KB	Output is correct
3	Correct	23 ms	82232 KB	Output is correct
4	Correct	46 ms	82628 KB	Output is correct
5	Correct	36 ms	83552 KB	Output is correct
6	Correct	16 ms	82100 KB	Output is correct
7	Correct	29 ms	82232 KB	Output is correct
8	Correct	29 ms	82100 KB	Output is correct
9	Correct	26 ms	82232 KB	Output is correct
10	Correct	43 ms	83552 KB	Output is correct
11	Correct	29 ms	82232 KB	Output is correct
12	Correct	69 ms	85268 KB	Output is correct
13	Correct	49 ms	83552 KB	Output is correct
14	Correct	36 ms	83552 KB	Output is correct
15	Correct	143 ms	89888 KB	Output is correct
16	Correct	199 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	39 ms	82892 KB	Output is correct
2	Correct	583 ms	118808 KB	Output is correct
3	Execution timed out	2000 ms	112856 KB	Execution timed out
4	Incorrect	656 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	29 ms	82760 KB	Output is correct
8	Correct	33 ms	82892 KB	Output is correct
9	Correct	36 ms	83420 KB	Output is correct
10	Correct	23 ms	82496 KB	Output is correct
11	Correct	23 ms	82496 KB	Output is correct
12	Correct	46 ms	83816 KB	Output is correct
13	Correct	536 ms	118808 KB	Output is correct
14	Correct	326 ms	103484 KB	Output is correct
15	Correct	306 ms	104408 KB	Output is correct
16	Correct	313 ms	99788 KB	Output is correct
17	Incorrect	989 ms	128564 KB	Output isn't correct
18	Incorrect	1012 ms	125132 KB	Output isn't correct
19	Incorrect	646 ms	106128 KB	Output isn't correct
20	Incorrect	666 ms	114836 KB	Output isn't correct
21	Incorrect	1293 ms	114044 KB	Output isn't correct
22	Execution timed out	2000 ms	237992 KB	Execution timed out
23	Incorrect	1403 ms	130016 KB	Output isn't correct
24	Incorrect	1363 ms	132920 KB	Output isn't correct
25	Execution timed out	2000 ms	126056 KB	Execution timed out
26	Correct	1486 ms	82100 KB	Output is correct
27	Correct	1939 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