Submission #59910

# Submission time Handle Problem Language Result Execution time Memory
59910 2018-07-23T10:02:52 Z Tenuun Mecho (IOI09_mecho) C++17
33 / 100
582 ms 6908 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();
		if(a[x][y]!=-1) continue;
		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'&& 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;
	}
	memset(a, -1, sizeof a);
	memset(bear, -1, sizeof bear);
	while(!q.empty())q.pop();
	while(!b.empty())b.pop();
	//check(l);
	/*for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cout << a[i][j] << " ";
		}
		cout << "\n";
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cout << bear[i][j] << " ";
		}
		cout << "\n";
	}*/
	if(!check(l)) cout << -1;
	else 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:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<bee.size(); i++){
               ~^~~~~~~~~~~
mecho.cpp:52: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 Correct 8 ms 5368 KB Output is correct
2 Correct 8 ms 5476 KB Output is correct
3 Correct 8 ms 5476 KB Output is correct
4 Correct 8 ms 5476 KB Output is correct
5 Correct 8 ms 5476 KB Output is correct
6 Incorrect 10 ms 5476 KB Output isn't correct
7 Correct 481 ms 6348 KB Output is correct
8 Correct 9 ms 6348 KB Output is correct
9 Correct 9 ms 6348 KB Output is correct
10 Correct 12 ms 6348 KB Output is correct
11 Correct 11 ms 6348 KB Output is correct
12 Incorrect 13 ms 6348 KB Output isn't correct
13 Incorrect 13 ms 6348 KB Output isn't correct
14 Correct 15 ms 6348 KB Output is correct
15 Incorrect 10 ms 6348 KB Output isn't correct
16 Incorrect 9 ms 6348 KB Output isn't correct
17 Incorrect 9 ms 6348 KB Output isn't correct
18 Incorrect 10 ms 6348 KB Output isn't correct
19 Incorrect 10 ms 6348 KB Output isn't correct
20 Incorrect 8 ms 6348 KB Output isn't correct
21 Incorrect 8 ms 6348 KB Output isn't correct
22 Incorrect 10 ms 6348 KB Output isn't correct
23 Incorrect 9 ms 6348 KB Output isn't correct
24 Incorrect 9 ms 6348 KB Output isn't correct
25 Incorrect 10 ms 6348 KB Output isn't correct
26 Incorrect 11 ms 6348 KB Output isn't correct
27 Incorrect 11 ms 6348 KB Output isn't correct
28 Incorrect 9 ms 6348 KB Output isn't correct
29 Incorrect 9 ms 6348 KB Output isn't correct
30 Incorrect 11 ms 6348 KB Output isn't correct
31 Incorrect 12 ms 6348 KB Output isn't correct
32 Incorrect 11 ms 6348 KB Output isn't correct
33 Incorrect 14 ms 6348 KB Output isn't correct
34 Incorrect 12 ms 6348 KB Output isn't correct
35 Correct 65 ms 6348 KB Output is correct
36 Incorrect 11 ms 6348 KB Output isn't correct
37 Incorrect 13 ms 6348 KB Output isn't correct
38 Correct 93 ms 6348 KB Output is correct
39 Incorrect 12 ms 6348 KB Output isn't correct
40 Incorrect 11 ms 6348 KB Output isn't correct
41 Correct 179 ms 6348 KB Output is correct
42 Incorrect 14 ms 6348 KB Output isn't correct
43 Incorrect 15 ms 6348 KB Output isn't correct
44 Correct 155 ms 6348 KB Output is correct
45 Incorrect 9 ms 6348 KB Output isn't correct
46 Incorrect 16 ms 6348 KB Output isn't correct
47 Correct 186 ms 6348 KB Output is correct
48 Incorrect 15 ms 6348 KB Output isn't correct
49 Incorrect 15 ms 6348 KB Output isn't correct
50 Correct 251 ms 6348 KB Output is correct
51 Incorrect 14 ms 6348 KB Output isn't correct
52 Incorrect 16 ms 6348 KB Output isn't correct
53 Correct 363 ms 6348 KB Output is correct
54 Incorrect 16 ms 6348 KB Output isn't correct
55 Incorrect 14 ms 6348 KB Output isn't correct
56 Correct 364 ms 6348 KB Output is correct
57 Incorrect 14 ms 6348 KB Output isn't correct
58 Incorrect 16 ms 6348 KB Output isn't correct
59 Correct 498 ms 6380 KB Output is correct
60 Incorrect 18 ms 6380 KB Output isn't correct
61 Incorrect 19 ms 6380 KB Output isn't correct
62 Correct 514 ms 6380 KB Output is correct
63 Correct 582 ms 6380 KB Output is correct
64 Correct 474 ms 6380 KB Output is correct
65 Correct 554 ms 6380 KB Output is correct
66 Correct 518 ms 6380 KB Output is correct
67 Correct 565 ms 6380 KB Output is correct
68 Correct 420 ms 6380 KB Output is correct
69 Correct 322 ms 6380 KB Output is correct
70 Correct 418 ms 6380 KB Output is correct
71 Correct 424 ms 6380 KB Output is correct
72 Incorrect 369 ms 6380 KB Output isn't correct
73 Incorrect 343 ms 6768 KB Output isn't correct
74 Incorrect 436 ms 6768 KB Output isn't correct
75 Incorrect 429 ms 6768 KB Output isn't correct
76 Incorrect 468 ms 6908 KB Output isn't correct
77 Incorrect 439 ms 6908 KB Output isn't correct
78 Correct 533 ms 6908 KB Output is correct
79 Correct 399 ms 6908 KB Output is correct
80 Correct 437 ms 6908 KB Output is correct
81 Incorrect 443 ms 6908 KB Output isn't correct
82 Incorrect 497 ms 6908 KB Output isn't correct
83 Correct 420 ms 6908 KB Output is correct
84 Correct 326 ms 6908 KB Output is correct
85 Correct 394 ms 6908 KB Output is correct
86 Correct 443 ms 6908 KB Output is correct
87 Correct 362 ms 6908 KB Output is correct
88 Correct 497 ms 6908 KB Output is correct
89 Correct 364 ms 6908 KB Output is correct
90 Correct 455 ms 6908 KB Output is correct
91 Correct 367 ms 6908 KB Output is correct
92 Correct 398 ms 6908 KB Output is correct