oj.uz

답안 #58185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58185 2018-07-17T06:15:57 Z gnoor Mecho (IOI09_mecho) C++17
42 / 100
 311 ms 9680 KB 
#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 (nextr==home.r&&nextc==home.c) 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
42.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8312 KB Output is correct
2 Correct 9 ms 8368 KB Output is correct
3 Correct 8 ms 8444 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 11 ms 8556 KB Output is correct
6 Correct 8 ms 8556 KB Output is correct
7 Correct 214 ms 9324 KB Output is correct
8 Correct 11 ms 9324 KB Output is correct
9 Correct 10 ms 9324 KB Output is correct
10 Correct 10 ms 9324 KB Output is correct
11 Correct 9 ms 9324 KB Output is correct
12 Incorrect 11 ms 9324 KB Output isn't correct
13 Incorrect 12 ms 9324 KB Output isn't correct
14 Correct 13 ms 9324 KB Output is correct
15 Incorrect 11 ms 9324 KB Output isn't correct
16 Incorrect 11 ms 9324 KB Output isn't correct
17 Incorrect 12 ms 9324 KB Output isn't correct
18 Incorrect 11 ms 9324 KB Output isn't correct
19 Incorrect 10 ms 9324 KB Output isn't correct
20 Incorrect 10 ms 9324 KB Output isn't correct
21 Incorrect 13 ms 9324 KB Output isn't correct
22 Incorrect 11 ms 9324 KB Output isn't correct
23 Incorrect 10 ms 9324 KB Output isn't correct
24 Incorrect 12 ms 9324 KB Output isn't correct
25 Incorrect 9 ms 9324 KB Output isn't correct
26 Incorrect 11 ms 9324 KB Output isn't correct
27 Incorrect 11 ms 9324 KB Output isn't correct
28 Incorrect 10 ms 9324 KB Output isn't correct
29 Incorrect 11 ms 9324 KB Output isn't correct
30 Incorrect 10 ms 9324 KB Output isn't correct
31 Incorrect 12 ms 9324 KB Output isn't correct
32 Incorrect 13 ms 9324 KB Output isn't correct
33 Incorrect 35 ms 9324 KB Output isn't correct
34 Incorrect 54 ms 9324 KB Output isn't correct
35 Correct 88 ms 9324 KB Output is correct
36 Incorrect 36 ms 9324 KB Output isn't correct
37 Incorrect 57 ms 9324 KB Output isn't correct
38 Correct 81 ms 9324 KB Output is correct
39 Incorrect 56 ms 9324 KB Output isn't correct
40 Incorrect 77 ms 9324 KB Output isn't correct
41 Correct 86 ms 9324 KB Output is correct
42 Incorrect 49 ms 9324 KB Output isn't correct
43 Incorrect 74 ms 9324 KB Output isn't correct
44 Correct 91 ms 9324 KB Output is correct
45 Incorrect 66 ms 9324 KB Output isn't correct
46 Incorrect 86 ms 9324 KB Output isn't correct
47 Correct 159 ms 9324 KB Output is correct
48 Incorrect 70 ms 9324 KB Output isn't correct
49 Incorrect 91 ms 9324 KB Output isn't correct
50 Correct 156 ms 9324 KB Output is correct
51 Incorrect 97 ms 9324 KB Output isn't correct
52 Incorrect 107 ms 9324 KB Output isn't correct
53 Correct 168 ms 9324 KB Output is correct
54 Incorrect 88 ms 9324 KB Output isn't correct
55 Incorrect 125 ms 9344 KB Output isn't correct
56 Correct 230 ms 9344 KB Output is correct
57 Incorrect 133 ms 9344 KB Output isn't correct
58 Incorrect 162 ms 9344 KB Output isn't correct
59 Correct 231 ms 9372 KB Output is correct
60 Incorrect 152 ms 9468 KB Output isn't correct
61 Incorrect 181 ms 9468 KB Output isn't correct
62 Correct 311 ms 9532 KB Output is correct
63 Correct 218 ms 9572 KB Output is correct
64 Correct 275 ms 9572 KB Output is correct
65 Correct 311 ms 9572 KB Output is correct
66 Correct 258 ms 9572 KB Output is correct
67 Correct 209 ms 9572 KB Output is correct
68 Correct 118 ms 9572 KB Output is correct
69 Correct 93 ms 9572 KB Output is correct
70 Correct 108 ms 9572 KB Output is correct
71 Correct 103 ms 9572 KB Output is correct
72 Incorrect 92 ms 9572 KB Output isn't correct
73 Incorrect 133 ms 9572 KB Output isn't correct
74 Correct 147 ms 9592 KB Output is correct
75 Correct 166 ms 9648 KB Output is correct
76 Correct 150 ms 9680 KB Output is correct
77 Correct 121 ms 9680 KB Output is correct
78 Correct 147 ms 9680 KB Output is correct
79 Correct 116 ms 9680 KB Output is correct
80 Correct 168 ms 9680 KB Output is correct
81 Correct 135 ms 9680 KB Output is correct
82 Correct 122 ms 9680 KB Output is correct
83 Correct 159 ms 9680 KB Output is correct
84 Correct 165 ms 9680 KB Output is correct
85 Correct 170 ms 9680 KB Output is correct
86 Correct 204 ms 9680 KB Output is correct
87 Correct 195 ms 9680 KB Output is correct
88 Correct 228 ms 9680 KB Output is correct
89 Correct 213 ms 9680 KB Output is correct
90 Correct 234 ms 9680 KB Output is correct
91 Correct 235 ms 9680 KB Output is correct
92 Correct 223 ms 9680 KB Output is correct