oj.uz

답안 #134085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134085 2019-07-22T04:12:45 Z wilwxk Tracks in the Snow (BOI13_tracks) C++14
69.375 / 100
 1975 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=4e3+5;
const int MAXNN=16000005;
unordered_set<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;
	tam[b]++;
}

void liga(int a, int b) {
	a=find(a); b=find(b);
	g[a].insert(b);
	g[b].insert(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]=i*m+j, tam[i*m+j]=1;

	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:40: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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 984 ms 889072 KB Output is correct
2 Correct 839 ms 877176 KB Output is correct
3 Correct 843 ms 877428 KB Output is correct
4 Correct 860 ms 882192 KB Output is correct
5 Correct 869 ms 880644 KB Output is correct
6 Correct 840 ms 877236 KB Output is correct
7 Correct 841 ms 877524 KB Output is correct
8 Correct 845 ms 877480 KB Output is correct
9 Correct 876 ms 877880 KB Output is correct
10 Correct 885 ms 880364 KB Output is correct
11 Correct 853 ms 878784 KB Output is correct
12 Correct 871 ms 882136 KB Output is correct
13 Correct 848 ms 880656 KB Output is correct
14 Correct 855 ms 880632 KB Output is correct
15 Correct 929 ms 888680 KB Output is correct
16 Correct 949 ms 889152 KB Output is correct
17 Correct 891 ms 887960 KB Output is correct
18 Correct 866 ms 882148 KB Output is correct

Subtask #2
39.375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 856 ms 893924 KB Output is correct
2 Correct 1172 ms 933220 KB Output is correct
3 Runtime error 922 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 1254 ms 978424 KB Output is correct
5 Runtime error 1076 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 895 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 858 ms 894416 KB Output is correct
8 Correct 860 ms 894060 KB Output is correct
9 Correct 848 ms 879036 KB Output is correct
10 Correct 842 ms 877860 KB Output is correct
11 Correct 878 ms 893944 KB Output is correct
12 Correct 845 ms 879264 KB Output is correct
13 Correct 1124 ms 933144 KB Output is correct
14 Correct 1008 ms 910600 KB Output is correct
15 Correct 1012 ms 913392 KB Output is correct
16 Correct 1014 ms 901472 KB Output is correct
17 Correct 1543 ms 1014848 KB Output is correct
18 Correct 1541 ms 1011584 KB Output is correct
19 Correct 1249 ms 978544 KB Output is correct
20 Correct 1201 ms 977772 KB Output is correct
21 Runtime error 1212 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 1074 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 1431 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 1149 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 916 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Correct 1669 ms 1026008 KB Output is correct
27 Runtime error 882 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 909 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 905 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 897 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 1975 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 883 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)