Submission #59896

# Submission time Handle Problem Language Result Execution time Memory
59896 2018-07-23T09:24:20 Z Tenuun Mecho (IOI09_mecho) C++11
16 / 100
510 ms 6780 KB
#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]);
                 ~^~~~~~~~~
# Verdict Execution time Memory 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