Submission #134063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134063	2019-07-22T03:46:08 Z	wilwxk	Tracks in the Snow (BOI13_tracks)	C++14	86.875 / 100	2000 ms	738908 KB

tracks

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

const int MAXN=5e3+3;
const int MAXNN=17000005;
vector<int> g[MAXNN];
short cor[MAXNN];
short marc[MAXNN];
short ori[MAXN][MAXN];
char c[MAXN];
int rep[MAXNN], tam[MAXNN], dist[MAXNN];
queue<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(find(0));
	dist[find(0)]=1;
	while(qu.size()) {
		int cur=qu.front(); qu.pop();
		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(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: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	515 ms	411412 KB	Output is correct
2	Correct	372 ms	399716 KB	Output is correct
3	Correct	372 ms	399876 KB	Output is correct
4	Correct	398 ms	405400 KB	Output is correct
5	Correct	388 ms	402544 KB	Output is correct
6	Correct	406 ms	399656 KB	Output is correct
7	Correct	431 ms	399932 KB	Output is correct
8	Correct	373 ms	400040 KB	Output is correct
9	Correct	377 ms	400124 KB	Output is correct
10	Correct	391 ms	402440 KB	Output is correct
11	Correct	384 ms	401316 KB	Output is correct
12	Correct	403 ms	404148 KB	Output is correct
13	Correct	387 ms	402668 KB	Output is correct
14	Correct	380 ms	402600 KB	Output is correct
15	Correct	441 ms	410256 KB	Output is correct
16	Correct	453 ms	411512 KB	Output is correct
17	Correct	419 ms	408064 KB	Output is correct
18	Correct	394 ms	405388 KB	Output is correct

Subtask #2

56.875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	390 ms	415924 KB	Output is correct
2	Correct	598 ms	446552 KB	Output is correct
3	Correct	1598 ms	723656 KB	Output is correct
4	Correct	708 ms	486548 KB	Output is correct
5	Correct	1533 ms	702708 KB	Output is correct
6	Execution timed out	2097 ms	677308 KB	Time limit exceeded
7	Correct	389 ms	416644 KB	Output is correct
8	Correct	386 ms	416048 KB	Output is correct
9	Correct	389 ms	401256 KB	Output is correct
10	Correct	374 ms	400172 KB	Output is correct
11	Correct	391 ms	416328 KB	Output is correct
12	Correct	375 ms	400872 KB	Output is correct
13	Correct	589 ms	446552 KB	Output is correct
14	Correct	495 ms	427628 KB	Output is correct
15	Correct	495 ms	426712 KB	Output is correct
16	Correct	491 ms	420488 KB	Output is correct
17	Correct	966 ms	513772 KB	Output is correct
18	Correct	864 ms	499480 KB	Output is correct
19	Correct	740 ms	486584 KB	Output is correct
20	Correct	647 ms	483840 KB	Output is correct
21	Correct	1055 ms	606440 KB	Output is correct
22	Correct	1506 ms	702816 KB	Output is correct
23	Correct	1472 ms	608172 KB	Output is correct
24	Correct	1054 ms	602316 KB	Output is correct
25	Execution timed out	2132 ms	738908 KB	Time limit exceeded
26	Correct	1264 ms	562552 KB	Output is correct
27	Correct	1602 ms	665032 KB	Output is correct
28	Execution timed out	2111 ms	674456 KB	Time limit exceeded
29	Execution timed out	2112 ms	703448 KB	Time limit exceeded
30	Execution timed out	2112 ms	738104 KB	Time limit exceeded
31	Execution timed out	2107 ms	669420 KB	Time limit exceeded
32	Correct	1551 ms	670300 KB	Output is correct