oj.uz

답안 #103688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103688 2019-04-02T04:30:31 Z tugushka Mecho (IOI09_mecho) C++14
4 / 100
 12 ms 4224 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;

using pii = pair < short, short >;
const int N = 805;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

char a[N][N];
pii mecho, home;
int n, s, hive[N][N];
bool used[N][N];

void hive_bfs(){
	memset( hive, -1, sizeof(hive) );
	queue < pii > q;
	for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++){
		if( a[i][j] == 'H' ){
			q.push( mp( i, j ) );
			hive[i][j] = 0;
		}
	}

	int dis = 0;
	while( !q.empty() ){
		dis += s;
		int sz = q.size();
		while( sz-- ){
			short int x, y;
			tie(x, y) = q.front();
			q.pop();
			for(int i = 0 ; i < 4 ; i++){
				short int tx = x+dx[i], ty = y+dy[i];
				if( tx < 0 || ty < 0 || tx >= n || ty >= n ) continue;
				if( a[tx][ty] == 'G' && hive[tx][ty] != -1 ){
					hive[tx][ty] = dis;
					q.push( mp( tx, ty ) );
				}
			}
		}
	}

	/*
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			if( hive[i][j] > 2e6 ) printf("@@ ");
			else printf("%2d ", hive[i][j]);
		}
		printf("\n");
	}
	*/
}

bool mecho_bfs(int start_time){
	memset( used, 0, sizeof(used) );

	if( start_time > hive[home.first][home.second] ){
		return false;
	}

	queue < pii > q;
	q.push( mecho );

	int dis = start_time;
	while( !q.empty() ){
		dis++;
		// cout << "dis " << dis << " : ";

		int sz = q.size();
		while( sz-- ){
			short int x, y;
			tie(x, y) = q.front();
			q.pop();
			for(int i = 0 ; i < 4 ; i++){
				short int tx = x+dx[i], ty = y+dy[i];
				if( tx < 0 || ty < 0 || tx >= n || ty >= n ) continue;
				if( !used[tx][ty] && a[tx][ty] == 'G' && hive[tx][ty] > dis ){
					used[tx][ty] = 1;
					if( used[ home.first ][ home.second ] ){
						return true;
					}
					// cout << "( " << tx << ',' << ty << " ), ";
					q.push( mp( tx, ty ) );
				}
			}
		}
		// cout << endl;
	}

	return used[ home.first ][ home.second ];
}

int main(){
	scanf("%d %d", &n, &s);
	for(int i = 0 ; i < n ; i++){
		scanf("%s", a[i]);
	}
	

	for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++){
		if( a[i][j] == 'D' ){
			home = mp( i, j );
		}
		if( a[i][j] == 'M' ){
			mecho = mp( i, j );
			a[i][j] = 'G';
		}
	}

	hive_bfs();
	hive[home.first][home.second] = 2e9;
	a[home.first][home.second] = 'G';

	if( !mecho_bfs( 0 ) ){
		printf("-1\n");
		return 0;
	}

	int l = 0, r = n*n, res;
	while( l <= r ){
		int mid = (l+r)/2;

		if( mecho_bfs( s*(mid) ) ){
			res = mid;
			l = mid+1;
		} else {
			r = mid-1;
		}
	}

	/*
	int res = 0;
	while( mecho_bfs( s*(res+1) ) ) res++;
	*/
	cout << res << endl;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:95: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:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
   ~~~~~^~~~~~~~~~~~
mecho.cpp:136:10: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << res << endl;
          ^~~

Subtask #1
4.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3456 KB Output isn't correct
2 Incorrect 5 ms 3456 KB Output isn't correct
3 Incorrect 5 ms 3456 KB Output isn't correct
4 Incorrect 6 ms 3456 KB Output isn't correct
5 Incorrect 5 ms 3456 KB Output isn't correct
6 Incorrect 5 ms 3456 KB Output isn't correct
7 Incorrect 10 ms 4096 KB Output isn't correct
8 Correct 5 ms 3456 KB Output is correct
9 Incorrect 5 ms 3456 KB Output isn't correct
10 Incorrect 5 ms 3584 KB Output isn't correct
11 Incorrect 5 ms 3584 KB Output isn't correct
12 Incorrect 5 ms 3584 KB Output isn't correct
13 Incorrect 5 ms 3584 KB Output isn't correct
14 Correct 5 ms 3584 KB Output is correct
15 Incorrect 6 ms 3584 KB Output isn't correct
16 Incorrect 5 ms 3456 KB Output isn't correct
17 Incorrect 5 ms 3584 KB Output isn't correct
18 Incorrect 5 ms 3456 KB Output isn't correct
19 Incorrect 5 ms 3456 KB Output isn't correct
20 Incorrect 5 ms 3584 KB Output isn't correct
21 Incorrect 5 ms 3456 KB Output isn't correct
22 Incorrect 5 ms 3584 KB Output isn't correct
23 Incorrect 5 ms 3584 KB Output isn't correct
24 Incorrect 6 ms 3584 KB Output isn't correct
25 Incorrect 5 ms 3584 KB Output isn't correct
26 Incorrect 4 ms 3584 KB Output isn't correct
27 Incorrect 5 ms 3584 KB Output isn't correct
28 Incorrect 5 ms 3584 KB Output isn't correct
29 Incorrect 4 ms 3584 KB Output isn't correct
30 Incorrect 6 ms 3584 KB Output isn't correct
31 Incorrect 4 ms 3584 KB Output isn't correct
32 Incorrect 5 ms 3584 KB Output isn't correct
33 Incorrect 5 ms 3712 KB Output isn't correct
34 Incorrect 5 ms 3712 KB Output isn't correct
35 Incorrect 5 ms 3840 KB Output isn't correct
36 Incorrect 7 ms 3840 KB Output isn't correct
37 Incorrect 7 ms 3840 KB Output isn't correct
38 Incorrect 6 ms 3840 KB Output isn't correct
39 Incorrect 8 ms 3968 KB Output isn't correct
40 Incorrect 7 ms 3840 KB Output isn't correct
41 Incorrect 5 ms 3840 KB Output isn't correct
42 Incorrect 7 ms 3968 KB Output isn't correct
43 Incorrect 7 ms 3840 KB Output isn't correct
44 Incorrect 6 ms 3840 KB Output isn't correct
45 Incorrect 8 ms 3960 KB Output isn't correct
46 Incorrect 6 ms 3968 KB Output isn't correct
47 Incorrect 6 ms 3968 KB Output isn't correct
48 Incorrect 6 ms 3968 KB Output isn't correct
49 Incorrect 7 ms 3968 KB Output isn't correct
50 Incorrect 7 ms 3968 KB Output isn't correct
51 Incorrect 7 ms 3968 KB Output isn't correct
52 Incorrect 7 ms 3968 KB Output isn't correct
53 Incorrect 7 ms 3968 KB Output isn't correct
54 Incorrect 7 ms 3968 KB Output isn't correct
55 Incorrect 7 ms 3968 KB Output isn't correct
56 Incorrect 7 ms 3968 KB Output isn't correct
57 Incorrect 8 ms 4096 KB Output isn't correct
58 Incorrect 11 ms 4096 KB Output isn't correct
59 Incorrect 10 ms 4096 KB Output isn't correct
60 Incorrect 9 ms 4096 KB Output isn't correct
61 Incorrect 9 ms 4096 KB Output isn't correct
62 Incorrect 9 ms 4124 KB Output isn't correct
63 Incorrect 8 ms 4096 KB Output isn't correct
64 Incorrect 12 ms 4084 KB Output isn't correct
65 Incorrect 9 ms 4096 KB Output isn't correct
66 Incorrect 9 ms 4096 KB Output isn't correct
67 Correct 9 ms 4096 KB Output is correct
68 Incorrect 9 ms 4068 KB Output isn't correct
69 Incorrect 8 ms 4096 KB Output isn't correct
70 Incorrect 10 ms 4216 KB Output isn't correct
71 Incorrect 8 ms 4096 KB Output isn't correct
72 Incorrect 7 ms 4096 KB Output isn't correct
73 Incorrect 8 ms 4096 KB Output isn't correct
74 Incorrect 9 ms 4096 KB Output isn't correct
75 Incorrect 8 ms 4096 KB Output isn't correct
76 Incorrect 8 ms 4096 KB Output isn't correct
77 Incorrect 9 ms 4096 KB Output isn't correct
78 Correct 8 ms 4096 KB Output is correct
79 Incorrect 8 ms 4096 KB Output isn't correct
80 Incorrect 10 ms 4096 KB Output isn't correct
81 Incorrect 8 ms 4096 KB Output isn't correct
82 Incorrect 9 ms 4096 KB Output isn't correct
83 Incorrect 9 ms 4096 KB Output isn't correct
84 Incorrect 8 ms 4100 KB Output isn't correct
85 Incorrect 9 ms 4096 KB Output isn't correct
86 Incorrect 8 ms 4096 KB Output isn't correct
87 Incorrect 8 ms 4096 KB Output isn't correct
88 Incorrect 8 ms 4224 KB Output isn't correct
89 Incorrect 8 ms 4172 KB Output isn't correct
90 Incorrect 9 ms 4096 KB Output isn't correct
91 Incorrect 8 ms 4096 KB Output isn't correct
92 Incorrect 8 ms 4096 KB Output isn't correct