답안 #59896 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59896	2018-07-23T09:24:20 Z	Tenuun	Mecho (IOI09_mecho)	C++11	16 / 100	510 ms	6780 KB

mecho

#include<bits/stdc++.h>

using namespace std;

int n, s, u, V, x, y, z;
int a[802][802], dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
int bear[802][802];

vector<string> v;
vector<pair<int, int> >bee, o;
queue<pair<int, int>>q, b;

bool BFS(){
	queue<pair<pair<int, int>, int> >t;
	t.push({{x, y}, 0});
	bear[x][y]=0;
	while(!t.empty()){
		if(t.front().second>=s) return false;
		x=t.front().first.first, y=t.front().first.second, z=t.front().second;
		t.pop();
		for(int i=0; i<4; i++){
			if(v[x+dx[i]][y+dy[i]]=='D') return true;
			if(v[x+dx[i]][y+dy[i]]=='G' && a[x+dx[i]][y+dy[i]]==-1 && bear[x+dx[i]][y+dy[i]]==-1){
				bear[x+dx[i]][y+dy[i]]=z+1;
				if(z+1>=s) o.push_back({x+dx[i], y+dy[i]});
				else t.push({{x+dx[i], y+dy[i]}, z+1});
			}
		}
	}
	return false;
}

bool check(int m){
	int curr;
	for(int i=0; i<bee.size(); i++){
		x=bee[i].first, y=bee[i].second;
		a[x][y]=0;
		q.push(bee[i]);
	}
	b.push({u, V});
	bear[u][V]=0;
	while(!q.empty()){
		x=q.front().first, y=q.front().second;
		curr=z=a[x][y];
		if(z>=m){
			while(!b.empty()){
				x=b.front().first, y=b.front().second;
				b.pop();
				if(BFS()) return true;
			}
			for(int i=0; i<o.size(); i++) b.push(o[i]);
			o.clear();
		}
		while(!q.empty() && a[q.front().first][q.front().second]==curr){
			x=q.front().first, y=q.front().second;
			q.pop();
			for(int i=0; i<4; i++){
				if((v[x+dx[i]][y+dy[i]]=='G' || v[x+dx[i]][y+dy[i]]=='M') && a[x+dx[i]][y+dy[i]]==-1){
					a[x+dx[i]][y+dy[i]]=a[x][y]+1;
					q.push({x+dx[i], y+dy[i]});
				}
			}
		}	
	}
	return false;
}

void solve(){
	int l=0, r=2*n, m=(l+r+1)/2;
	while(l<r){
		memset(a, -1, sizeof a);
		memset(bear, -1, sizeof bear);
		while(!q.empty())q.pop();
		while(!b.empty())b.pop();
		if(check(m)) l=m;
		else r=m-1;
		m=(l+r+1)/2;
	}
	cout << l;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s;
	string tmp, k;
	for(int i=0; i<n+2; i++) tmp+='T';
	v.push_back(tmp);
	for(int i=1; i<=n; i++){
		cin >> k;
		k='T'+k+'T';
		for(int j=1; j<=n; j++){
			if(k[j]=='M'){
				u=i, V=j;
			}
			if(k[j]=='H'){
				bee.push_back({i, j});
			}
		}
		v.push_back(k);
	}
	v.push_back(tmp);
	solve();
	return 0;
}

Compilation message

mecho.cpp: In function 'bool check(int)':
mecho.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<bee.size(); i++){
               ~^~~~~~~~~~~
mecho.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<o.size(); i++) b.push(o[i]);
                 ~^~~~~~~~~

Subtask #1
16.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	5368 KB	Output isn't correct
2	Incorrect	11 ms	5588 KB	Output isn't correct
3	Incorrect	8 ms	5588 KB	Output isn't correct
4	Incorrect	9 ms	5612 KB	Output isn't correct
5	Correct	9 ms	5612 KB	Output is correct
6	Incorrect	10 ms	5612 KB	Output isn't correct
7	Correct	369 ms	6304 KB	Output is correct
8	Incorrect	9 ms	6304 KB	Output isn't correct
9	Correct	9 ms	6304 KB	Output is correct
10	Correct	8 ms	6304 KB	Output is correct
11	Correct	9 ms	6304 KB	Output is correct
12	Incorrect	10 ms	6304 KB	Output isn't correct
13	Incorrect	12 ms	6304 KB	Output isn't correct
14	Incorrect	10 ms	6304 KB	Output isn't correct
15	Incorrect	8 ms	6304 KB	Output isn't correct
16	Incorrect	8 ms	6304 KB	Output isn't correct
17	Incorrect	9 ms	6304 KB	Output isn't correct
18	Incorrect	9 ms	6304 KB	Output isn't correct
19	Incorrect	11 ms	6304 KB	Output isn't correct
20	Incorrect	7 ms	6304 KB	Output isn't correct
21	Incorrect	10 ms	6304 KB	Output isn't correct
22	Incorrect	9 ms	6304 KB	Output isn't correct
23	Incorrect	9 ms	6304 KB	Output isn't correct
24	Incorrect	10 ms	6304 KB	Output isn't correct
25	Incorrect	10 ms	6304 KB	Output isn't correct
26	Incorrect	8 ms	6304 KB	Output isn't correct
27	Incorrect	10 ms	6304 KB	Output isn't correct
28	Incorrect	11 ms	6304 KB	Output isn't correct
29	Incorrect	10 ms	6304 KB	Output isn't correct
30	Incorrect	10 ms	6304 KB	Output isn't correct
31	Incorrect	9 ms	6304 KB	Output isn't correct
32	Incorrect	11 ms	6304 KB	Output isn't correct
33	Incorrect	12 ms	6304 KB	Output isn't correct
34	Incorrect	12 ms	6304 KB	Output isn't correct
35	Correct	72 ms	6304 KB	Output is correct
36	Incorrect	11 ms	6304 KB	Output isn't correct
37	Incorrect	11 ms	6304 KB	Output isn't correct
38	Correct	87 ms	6304 KB	Output is correct
39	Incorrect	14 ms	6304 KB	Output isn't correct
40	Incorrect	14 ms	6304 KB	Output isn't correct
41	Correct	134 ms	6304 KB	Output is correct
42	Incorrect	13 ms	6304 KB	Output isn't correct
43	Incorrect	13 ms	6304 KB	Output isn't correct
44	Correct	139 ms	6304 KB	Output is correct
45	Incorrect	12 ms	6304 KB	Output isn't correct
46	Incorrect	12 ms	6304 KB	Output isn't correct
47	Correct	228 ms	6304 KB	Output is correct
48	Incorrect	12 ms	6304 KB	Output isn't correct
49	Incorrect	15 ms	6304 KB	Output isn't correct
50	Correct	245 ms	6304 KB	Output is correct
51	Incorrect	14 ms	6304 KB	Output isn't correct
52	Incorrect	15 ms	6304 KB	Output isn't correct
53	Correct	235 ms	6304 KB	Output is correct
54	Incorrect	15 ms	6304 KB	Output isn't correct
55	Incorrect	16 ms	6304 KB	Output isn't correct
56	Correct	293 ms	6304 KB	Output is correct
57	Incorrect	13 ms	6304 KB	Output isn't correct
58	Incorrect	18 ms	6304 KB	Output isn't correct
59	Correct	367 ms	6304 KB	Output is correct
60	Incorrect	16 ms	6304 KB	Output isn't correct
61	Incorrect	15 ms	6304 KB	Output isn't correct
62	Correct	379 ms	6304 KB	Output is correct
63	Correct	436 ms	6312 KB	Output is correct
64	Correct	378 ms	6312 KB	Output is correct
65	Correct	510 ms	6312 KB	Output is correct
66	Incorrect	490 ms	6312 KB	Output isn't correct
67	Incorrect	478 ms	6372 KB	Output isn't correct
68	Correct	351 ms	6396 KB	Output is correct
69	Correct	307 ms	6400 KB	Output is correct
70	Correct	322 ms	6400 KB	Output is correct
71	Correct	301 ms	6400 KB	Output is correct
72	Incorrect	370 ms	6400 KB	Output isn't correct
73	Incorrect	267 ms	6652 KB	Output isn't correct
74	Incorrect	328 ms	6652 KB	Output isn't correct
75	Incorrect	462 ms	6652 KB	Output isn't correct
76	Incorrect	296 ms	6780 KB	Output isn't correct
77	Incorrect	315 ms	6780 KB	Output isn't correct
78	Incorrect	416 ms	6780 KB	Output isn't correct
79	Correct	335 ms	6780 KB	Output is correct
80	Correct	346 ms	6780 KB	Output is correct
81	Correct	361 ms	6780 KB	Output is correct
82	Incorrect	345 ms	6780 KB	Output isn't correct
83	Correct	445 ms	6780 KB	Output is correct
84	Correct	342 ms	6780 KB	Output is correct
85	Correct	376 ms	6780 KB	Output is correct
86	Correct	385 ms	6780 KB	Output is correct
87	Correct	413 ms	6780 KB	Output is correct
88	Correct	444 ms	6780 KB	Output is correct
89	Correct	366 ms	6780 KB	Output is correct
90	Correct	358 ms	6780 KB	Output is correct
91	Correct	392 ms	6780 KB	Output is correct
92	Correct	484 ms	6780 KB	Output is correct

답안 #59896

Compilation message

Subtask #1 16.0 / 100.0

Subtask #1
16.0 / 100.0