Submission #134067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134067	2019-07-22T03:49:10 Z	wilwxk	Tracks in the Snow (BOI13_tracks)	C++14	71.5625 / 100	2000 ms	702904 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++];
		cur=find(cur);
		if(marc[cur]==2) continue; marc[cur]=2; 
		respf=max(respf, dist[cur]);

		for(auto viz : g[cur]) {
			if(marc[find(viz)]!=0) continue;
			qu.push_back(find(viz));
			dist[viz]=dist[cur]+1;
			marc[find(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:42:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(marc[cur]==2) continue; marc[cur]=2; 
   ^~
tracks.cpp:42: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:55: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:61: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	434 ms	388088 KB	Output is correct
2	Correct	354 ms	376176 KB	Output is correct
3	Correct	352 ms	376416 KB	Output is correct
4	Correct	380 ms	381736 KB	Output is correct
5	Correct	362 ms	379224 KB	Output is correct
6	Correct	360 ms	376132 KB	Output is correct
7	Correct	378 ms	376392 KB	Output is correct
8	Correct	357 ms	376568 KB	Output is correct
9	Correct	350 ms	376700 KB	Output is correct
10	Correct	403 ms	378828 KB	Output is correct
11	Correct	372 ms	377976 KB	Output is correct
12	Correct	383 ms	380880 KB	Output is correct
13	Correct	411 ms	379148 KB	Output is correct
14	Correct	367 ms	379256 KB	Output is correct
15	Correct	423 ms	387128 KB	Output is correct
16	Correct	428 ms	388344 KB	Output is correct
17	Correct	401 ms	384944 KB	Output is correct
18	Correct	409 ms	382084 KB	Output is correct

Subtask #2

41.5625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	387 ms	392568 KB	Output is correct
2	Correct	668 ms	424140 KB	Output is correct
3	Execution timed out	2103 ms	588252 KB	Time limit exceeded
4	Correct	923 ms	463120 KB	Output is correct
5	Execution timed out	2098 ms	701740 KB	Time limit exceeded
6	Execution timed out	2085 ms	569204 KB	Time limit exceeded
7	Correct	367 ms	393196 KB	Output is correct
8	Correct	370 ms	392696 KB	Output is correct
9	Correct	361 ms	377792 KB	Output is correct
10	Correct	423 ms	376696 KB	Output is correct
11	Correct	368 ms	392952 KB	Output is correct
12	Correct	353 ms	377592 KB	Output is correct
13	Correct	638 ms	424272 KB	Output is correct
14	Correct	515 ms	404720 KB	Output is correct
15	Correct	518 ms	404296 KB	Output is correct
16	Correct	484 ms	397404 KB	Output is correct
17	Correct	1223 ms	491960 KB	Output is correct
18	Correct	1101 ms	479844 KB	Output is correct
19	Correct	895 ms	464068 KB	Output is correct
20	Correct	923 ms	461752 KB	Output is correct
21	Correct	1762 ms	579724 KB	Output is correct
22	Execution timed out	2097 ms	702904 KB	Time limit exceeded
23	Execution timed out	2063 ms	581088 KB	Time limit exceeded
24	Correct	1612 ms	576152 KB	Output is correct
25	Execution timed out	2064 ms	567672 KB	Time limit exceeded
26	Execution timed out	2065 ms	524120 KB	Time limit exceeded
27	Execution timed out	2097 ms	565076 KB	Time limit exceeded
28	Execution timed out	2081 ms	564960 KB	Time limit exceeded
29	Execution timed out	2080 ms	564996 KB	Time limit exceeded
30	Execution timed out	2097 ms	560760 KB	Time limit exceeded
31	Execution timed out	2094 ms	528760 KB	Time limit exceeded
32	Execution timed out	2097 ms	564028 KB	Time limit exceeded