답안 #59903 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59903	2018-07-23T09:38:53 Z	Tenuun	Mecho (IOI09_mecho)	C++17	20 / 100	623 ms	6904 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' && 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();
		//cout << m << " " << check(m) << endl;
		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)==false) 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: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
20.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	5368 KB	Output isn't correct
2	Incorrect	9 ms	5476 KB	Output isn't correct
3	Incorrect	11 ms	5536 KB	Output isn't correct
4	Incorrect	10 ms	5536 KB	Output isn't correct
5	Correct	11 ms	5536 KB	Output is correct
6	Incorrect	10 ms	5540 KB	Output isn't correct
7	Correct	535 ms	6436 KB	Output is correct
8	Incorrect	12 ms	6436 KB	Output isn't correct
9	Correct	8 ms	6436 KB	Output is correct
10	Correct	11 ms	6436 KB	Output is correct
11	Correct	9 ms	6436 KB	Output is correct
12	Incorrect	12 ms	6436 KB	Output isn't correct
13	Incorrect	13 ms	6436 KB	Output isn't correct
14	Correct	12 ms	6436 KB	Output is correct
15	Incorrect	10 ms	6436 KB	Output isn't correct
16	Incorrect	10 ms	6436 KB	Output isn't correct
17	Incorrect	10 ms	6436 KB	Output isn't correct
18	Incorrect	11 ms	6436 KB	Output isn't correct
19	Incorrect	11 ms	6436 KB	Output isn't correct
20	Incorrect	10 ms	6436 KB	Output isn't correct
21	Incorrect	10 ms	6436 KB	Output isn't correct
22	Incorrect	11 ms	6436 KB	Output isn't correct
23	Incorrect	11 ms	6436 KB	Output isn't correct
24	Incorrect	11 ms	6436 KB	Output isn't correct
25	Incorrect	11 ms	6436 KB	Output isn't correct
26	Incorrect	10 ms	6436 KB	Output isn't correct
27	Incorrect	10 ms	6436 KB	Output isn't correct
28	Incorrect	11 ms	6436 KB	Output isn't correct
29	Incorrect	11 ms	6436 KB	Output isn't correct
30	Incorrect	11 ms	6436 KB	Output isn't correct
31	Incorrect	11 ms	6436 KB	Output isn't correct
32	Incorrect	12 ms	6436 KB	Output isn't correct
33	Incorrect	12 ms	6436 KB	Output isn't correct
34	Incorrect	13 ms	6436 KB	Output isn't correct
35	Correct	75 ms	6436 KB	Output is correct
36	Incorrect	13 ms	6436 KB	Output isn't correct
37	Incorrect	12 ms	6436 KB	Output isn't correct
38	Correct	114 ms	6436 KB	Output is correct
39	Incorrect	13 ms	6436 KB	Output isn't correct
40	Incorrect	14 ms	6436 KB	Output isn't correct
41	Correct	157 ms	6436 KB	Output is correct
42	Incorrect	14 ms	6436 KB	Output isn't correct
43	Incorrect	12 ms	6436 KB	Output isn't correct
44	Correct	202 ms	6436 KB	Output is correct
45	Incorrect	13 ms	6436 KB	Output isn't correct
46	Incorrect	18 ms	6436 KB	Output isn't correct
47	Correct	280 ms	6436 KB	Output is correct
48	Incorrect	14 ms	6436 KB	Output isn't correct
49	Incorrect	15 ms	6436 KB	Output isn't correct
50	Correct	237 ms	6436 KB	Output is correct
51	Incorrect	15 ms	6436 KB	Output isn't correct
52	Incorrect	16 ms	6436 KB	Output isn't correct
53	Correct	324 ms	6436 KB	Output is correct
54	Incorrect	14 ms	6436 KB	Output isn't correct
55	Incorrect	16 ms	6436 KB	Output isn't correct
56	Correct	351 ms	6436 KB	Output is correct
57	Incorrect	16 ms	6436 KB	Output isn't correct
58	Incorrect	17 ms	6436 KB	Output isn't correct
59	Correct	450 ms	6436 KB	Output is correct
60	Incorrect	14 ms	6436 KB	Output isn't correct
61	Incorrect	16 ms	6436 KB	Output isn't correct
62	Correct	468 ms	6436 KB	Output is correct
63	Correct	587 ms	6436 KB	Output is correct
64	Correct	431 ms	6436 KB	Output is correct
65	Correct	609 ms	6436 KB	Output is correct
66	Incorrect	456 ms	6436 KB	Output isn't correct
67	Correct	564 ms	6436 KB	Output is correct
68	Correct	383 ms	6436 KB	Output is correct
69	Correct	389 ms	6436 KB	Output is correct
70	Correct	401 ms	6436 KB	Output is correct
71	Correct	391 ms	6436 KB	Output is correct
72	Incorrect	396 ms	6436 KB	Output isn't correct
73	Incorrect	275 ms	6640 KB	Output isn't correct
74	Incorrect	402 ms	6640 KB	Output isn't correct
75	Incorrect	559 ms	6648 KB	Output isn't correct
76	Incorrect	598 ms	6760 KB	Output isn't correct
77	Incorrect	425 ms	6904 KB	Output isn't correct
78	Correct	463 ms	6904 KB	Output is correct
79	Correct	305 ms	6904 KB	Output is correct
80	Correct	423 ms	6904 KB	Output is correct
81	Correct	427 ms	6904 KB	Output is correct
82	Incorrect	317 ms	6904 KB	Output isn't correct
83	Correct	443 ms	6904 KB	Output is correct
84	Correct	449 ms	6904 KB	Output is correct
85	Correct	468 ms	6904 KB	Output is correct
86	Correct	475 ms	6904 KB	Output is correct
87	Correct	441 ms	6904 KB	Output is correct
88	Correct	414 ms	6904 KB	Output is correct
89	Correct	336 ms	6904 KB	Output is correct
90	Correct	416 ms	6904 KB	Output is correct
91	Correct	470 ms	6904 KB	Output is correct
92	Correct	623 ms	6904 KB	Output is correct

답안 #59903

Compilation message

Subtask #1 20.0 / 100.0

Subtask #1
20.0 / 100.0