답안 #58184 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58184	2018-07-17T06:11:48 Z	gnoor	Mecho (IOI09_mecho)	C++17	31 / 100	338 ms	17920 KB

mecho

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct cell {
	int r,c;
};

queue<cell> bee;
queue<cell> bear;
bool wall[1010][1010];

int disBear[1010][1010];
int disBee[1010][1010];
cell home;
cell start;

int di[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int n,s;

bool check(int x) {
	memset(disBear,63,sizeof(disBear));
	disBear[start.r][start.c]=x*s;
	bear.push(start);
	int nowr,nowc,nextr,nextc;
	while (!bear.empty()) {
		nowr=bear.front().r;
		nowc=bear.front().c;
		bear.pop();
		for (int i=0;i<4;i++) {
			nextr=nowr+di[i][0];
			nextc=nowc+di[i][1];
			if (nextc<0||nextc>=n||nextr<0||nextr>=n) continue;
			if (wall[nextr][nextc]) continue;
			if (disBear[nextr][nextc]<=disBear[nowr][nowc]+1) continue;
			if (disBee[nextr][nextc]<=(disBear[nowr][nowc]+1)/s) continue;
			disBear[nextr][nextc]=disBear[nowr][nowc]+1;
			bear.push(cell{nextr,nextc});
		}
	}

	return disBear[home.r][home.c]!=0x3f3f3f3f;
}

int main () {
	scanf("%d%d",&n,&s);
	char x;
	

	memset(disBee,63,sizeof(disBee));
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++) {
			scanf(" %c",&x);
			if (x=='T') wall[i][j]=true;
			else if (x=='M'){
				start=cell{i,j};
			}
			else if (x=='D') home=cell{i,j};
			else if (x=='H') {
				bee.push(cell{i,j});
				disBee[i][j]=0;
			}
		}
	}


	int nowr,nowc;
	int nextr,nextc;
	while (!bee.empty()) {
		nowr=bee.front().r;
		nowc=bee.front().c;
		bee.pop();
		for (int i=0;i<4;i++) {
			nextr=nowr+di[i][0];
			nextc=nowc+di[i][1];
			if (nextc<0||nextc>=n||nextr<0||nextr>=n) continue;
			if (wall[nextr][nextc]) continue;
			if (disBee[nextr][nextc]<=disBee[nowr][nowc]+1) continue;
			disBee[nextr][nextc]=disBee[nowr][nowc]+1;
			bee.push(cell{nextr,nextc});
		}
	}

	int lo=0;
	int hi=2*n;
	int mid;	
	while (lo<hi) {
		mid=(lo+hi+1)>>1;
		if (check(mid)) {
			lo=mid;
		} else {
			hi=mid-1;
		}
	}
	if (check(lo)) printf("%d\n",lo);
	else printf("-1\n");


	return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&s);
  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&x);
    ~~~~~^~~~~~~~~~

Subtask #1
31.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	8312 KB	Output is correct
2	Incorrect	9 ms	8312 KB	Output isn't correct
3	Correct	8 ms	8380 KB	Output is correct
4	Incorrect	9 ms	8588 KB	Output isn't correct
5	Correct	10 ms	8588 KB	Output is correct
6	Incorrect	9 ms	8588 KB	Output isn't correct
7	Incorrect	176 ms	9852 KB	Output isn't correct
8	Correct	12 ms	9852 KB	Output is correct
9	Correct	9 ms	9852 KB	Output is correct
10	Correct	11 ms	9852 KB	Output is correct
11	Correct	11 ms	9852 KB	Output is correct
12	Incorrect	12 ms	9852 KB	Output isn't correct
13	Incorrect	12 ms	9852 KB	Output isn't correct
14	Correct	13 ms	9852 KB	Output is correct
15	Incorrect	12 ms	9852 KB	Output isn't correct
16	Incorrect	12 ms	9852 KB	Output isn't correct
17	Incorrect	11 ms	9852 KB	Output isn't correct
18	Incorrect	10 ms	9852 KB	Output isn't correct
19	Incorrect	10 ms	9852 KB	Output isn't correct
20	Incorrect	11 ms	9852 KB	Output isn't correct
21	Incorrect	12 ms	9852 KB	Output isn't correct
22	Incorrect	11 ms	9852 KB	Output isn't correct
23	Incorrect	10 ms	9852 KB	Output isn't correct
24	Incorrect	10 ms	9852 KB	Output isn't correct
25	Incorrect	10 ms	9852 KB	Output isn't correct
26	Incorrect	10 ms	9852 KB	Output isn't correct
27	Incorrect	12 ms	9852 KB	Output isn't correct
28	Incorrect	13 ms	9852 KB	Output isn't correct
29	Incorrect	15 ms	9852 KB	Output isn't correct
30	Incorrect	12 ms	9852 KB	Output isn't correct
31	Incorrect	13 ms	9852 KB	Output isn't correct
32	Incorrect	11 ms	9852 KB	Output isn't correct
33	Incorrect	28 ms	9852 KB	Output isn't correct
34	Incorrect	53 ms	9852 KB	Output isn't correct
35	Correct	80 ms	9984 KB	Output is correct
36	Incorrect	40 ms	10220 KB	Output isn't correct
37	Incorrect	64 ms	10372 KB	Output isn't correct
38	Correct	82 ms	10668 KB	Output is correct
39	Incorrect	68 ms	10820 KB	Output isn't correct
40	Incorrect	100 ms	10988 KB	Output isn't correct
41	Correct	109 ms	11260 KB	Output is correct
42	Incorrect	59 ms	11556 KB	Output isn't correct
43	Incorrect	95 ms	11804 KB	Output isn't correct
44	Correct	83 ms	12044 KB	Output is correct
45	Incorrect	55 ms	12408 KB	Output isn't correct
46	Incorrect	75 ms	12620 KB	Output isn't correct
47	Correct	117 ms	13024 KB	Output is correct
48	Incorrect	83 ms	13316 KB	Output isn't correct
49	Incorrect	131 ms	13800 KB	Output isn't correct
50	Correct	182 ms	14212 KB	Output is correct
51	Incorrect	93 ms	14512 KB	Output isn't correct
52	Incorrect	181 ms	15056 KB	Output isn't correct
53	Correct	162 ms	15344 KB	Output is correct
54	Incorrect	149 ms	15888 KB	Output isn't correct
55	Incorrect	144 ms	16444 KB	Output isn't correct
56	Correct	193 ms	16900 KB	Output is correct
57	Incorrect	103 ms	17496 KB	Output isn't correct
58	Incorrect	133 ms	17496 KB	Output isn't correct
59	Correct	274 ms	17660 KB	Output is correct
60	Incorrect	105 ms	17660 KB	Output isn't correct
61	Incorrect	151 ms	17660 KB	Output isn't correct
62	Correct	231 ms	17660 KB	Output is correct
63	Correct	180 ms	17660 KB	Output is correct
64	Correct	306 ms	17660 KB	Output is correct
65	Correct	305 ms	17684 KB	Output is correct
66	Correct	338 ms	17684 KB	Output is correct
67	Correct	262 ms	17684 KB	Output is correct
68	Correct	134 ms	17684 KB	Output is correct
69	Correct	92 ms	17684 KB	Output is correct
70	Correct	99 ms	17684 KB	Output is correct
71	Correct	82 ms	17684 KB	Output is correct
72	Incorrect	74 ms	17684 KB	Output isn't correct
73	Incorrect	92 ms	17816 KB	Output isn't correct
74	Correct	111 ms	17816 KB	Output is correct
75	Correct	133 ms	17816 KB	Output is correct
76	Correct	169 ms	17816 KB	Output is correct
77	Correct	175 ms	17920 KB	Output is correct
78	Correct	170 ms	17920 KB	Output is correct
79	Correct	196 ms	17920 KB	Output is correct
80	Correct	149 ms	17920 KB	Output is correct
81	Correct	171 ms	17920 KB	Output is correct
82	Correct	135 ms	17920 KB	Output is correct
83	Correct	181 ms	17920 KB	Output is correct
84	Correct	226 ms	17920 KB	Output is correct
85	Correct	163 ms	17920 KB	Output is correct
86	Correct	201 ms	17920 KB	Output is correct
87	Correct	166 ms	17920 KB	Output is correct
88	Correct	212 ms	17920 KB	Output is correct
89	Correct	197 ms	17920 KB	Output is correct
90	Correct	223 ms	17920 KB	Output is correct
91	Correct	239 ms	17920 KB	Output is correct
92	Correct	178 ms	17920 KB	Output is correct

답안 #58184

Compilation message

Subtask #1 31.0 / 100.0

Subtask #1
31.0 / 100.0