Submission #134070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134070	2019-07-22T03:51:22 Z	wilwxk	Tracks in the Snow (BOI13_tracks)	C++14	73.75 / 100	2000 ms	697536 KB

tracks

#include <bits/stdc++.h>
using namespace std;

const int MAXN=4e3+5;
const int MAXNN=16000005;
vector<int> g[MAXNN];
short cor[MAXNN];
short marc[MAXNN];
short ori[MAXN][MAXN];
char c[MAXN];
int rep[MAXNN], tam[MAXNN], dist[MAXNN];
vector<int> qu;
int dx[]={0, 1, 0, -1};
int dy[]={1, 0, -1, 0};
int n, m, respf;

int find(int cur) {
	if(rep[cur]==cur) return cur;
	return rep[cur]=find(rep[cur]);
}
void une(int a, int b) {
	a=find(a); b=find(b);
	if(a==b) return;
	if(tam[a]<tam[b]) swap(a, b);
	rep[a]=b;
}

void liga(int a, int b) {
	a=find(a); b=find(b);
	g[a].push_back(b);
	g[b].push_back(a);
	// printf("liga %d %d\n", a, b);
}

void bfs() {
	qu.push_back(find(0));
	dist[find(0)]=1;
	int ind=0;
	while(ind<qu.size()) {
		int cur=qu[ind++];
		if(marc[cur]==2) continue; marc[cur]=2; 
		respf=max(respf, dist[cur]);

		for(auto viz : g[cur]) {
			if(marc[viz]!=0) continue;
			qu.push_back(viz);
			dist[viz]=dist[cur]+1;
			marc[viz]=1;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	srand(time(0));
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) rep[i*m+j]=tam[i*m+j]=i*m+j;
	random_shuffle(tam, tam+(n*m));

	for(int i=0; i<n; i++) {
		scanf(" %s", c);
		for(int j=0; j<m; j++) {
			if(c[j]=='.') ori[i][j]=0;
			else if(c[j]=='F') ori[i][j]=1;
			else ori[i][j]=2;
			cor[i*m+j]=ori[i][j];
		}
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			int cur=i*m+j;
			if(!cor[cur]) continue;
			for(int k=0; k<4; k++) {
				int ii=i+dx[k]; int jj=j+dy[k];
				if(ii<0||jj<0||ii>=n||jj>=m) continue;
				int viz=ii*m+jj;
				if(!cor[viz]) continue;

				if(ori[i][j]==ori[ii][jj]) une(cur, viz);
			}
		}
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			int cur=i*m+j;
			if(!cor[cur]) continue;
			for(int k=0; k<4; k++) {
				int ii=i+dx[k]; int jj=j+dy[k];
				if(ii<0||jj<0||ii>=n||jj>=m) continue;
				int viz=ii*m+jj;
				if(!cor[viz]) continue;

				if(cor[cur]!=cor[viz]) liga(cur, viz);
			}
		}
	}

	n*=m;
	bfs();

	printf("%d\n", respf);
}

Compilation message

tracks.cpp: In function 'void bfs()':
tracks.cpp:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ind<qu.size()) {
        ~~~^~~~~~~~~~
tracks.cpp:41:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(marc[cur]==2) continue; marc[cur]=2; 
   ^~
tracks.cpp:41:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(marc[cur]==2) continue; marc[cur]=2; 
                              ^~~~
tracks.cpp: In function 'int main()':
tracks.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", c);
   ~~~~~^~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	427 ms	388244 KB	Output is correct
2	Correct	351 ms	376196 KB	Output is correct
3	Correct	346 ms	376360 KB	Output is correct
4	Correct	387 ms	381724 KB	Output is correct
5	Correct	360 ms	379128 KB	Output is correct
6	Correct	351 ms	376152 KB	Output is correct
7	Correct	350 ms	376312 KB	Output is correct
8	Correct	348 ms	376568 KB	Output is correct
9	Correct	351 ms	376696 KB	Output is correct
10	Correct	359 ms	378872 KB	Output is correct
11	Correct	356 ms	377760 KB	Output is correct
12	Correct	377 ms	380764 KB	Output is correct
13	Correct	373 ms	379152 KB	Output is correct
14	Correct	366 ms	379128 KB	Output is correct
15	Correct	444 ms	386928 KB	Output is correct
16	Correct	427 ms	388132 KB	Output is correct
17	Correct	397 ms	384888 KB	Output is correct
18	Correct	376 ms	381912 KB	Output is correct

Subtask #2

43.75 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	369 ms	392568 KB	Output is correct
2	Correct	619 ms	422652 KB	Output is correct
3	Execution timed out	2106 ms	582136 KB	Time limit exceeded
4	Correct	830 ms	460392 KB	Output is correct
5	Execution timed out	2110 ms	697500 KB	Time limit exceeded
6	Execution timed out	2108 ms	563960 KB	Time limit exceeded
7	Correct	370 ms	393208 KB	Output is correct
8	Correct	371 ms	392580 KB	Output is correct
9	Correct	357 ms	377720 KB	Output is correct
10	Correct	357 ms	376696 KB	Output is correct
11	Correct	371 ms	392888 KB	Output is correct
12	Correct	353 ms	377464 KB	Output is correct
13	Correct	637 ms	422640 KB	Output is correct
14	Correct	506 ms	404040 KB	Output is correct
15	Correct	536 ms	403316 KB	Output is correct
16	Correct	482 ms	396992 KB	Output is correct
17	Correct	1124 ms	488292 KB	Output is correct
18	Correct	1053 ms	476044 KB	Output is correct
19	Correct	836 ms	460648 KB	Output is correct
20	Correct	793 ms	458468 KB	Output is correct
21	Correct	1642 ms	574048 KB	Output is correct
22	Execution timed out	2091 ms	697536 KB	Time limit exceeded
23	Correct	1938 ms	577264 KB	Output is correct
24	Correct	1591 ms	572700 KB	Output is correct
25	Execution timed out	2105 ms	575568 KB	Time limit exceeded
26	Execution timed out	2037 ms	523580 KB	Time limit exceeded
27	Execution timed out	2117 ms	564156 KB	Time limit exceeded
28	Execution timed out	2100 ms	564044 KB	Time limit exceeded
29	Execution timed out	2092 ms	564000 KB	Time limit exceeded
30	Execution timed out	2101 ms	560196 KB	Time limit exceeded
31	Execution timed out	2100 ms	536668 KB	Time limit exceeded
32	Execution timed out	2106 ms	564096 KB	Time limit exceeded