oj.uz

Submission #103669

# Submission time Handle Problem Language Result Execution time Memory
103669 2019-04-02T03:52:01 Z tugushka Mecho (IOI09_mecho) C++14
3 / 100
 1000 ms 66560 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;

using pii = pair < int, int >;
const int N = 1005;
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];

void hive_bfs(){
	memset( hive, 11, 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-- ){
			int x, y;
			tie(x, y) = q.front();
			q.pop();
			for(int i = 0 ; i < 4 ; i++){
				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] > 2e6 ){
					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){
	bool used[N][N];
	memset( used, 0, sizeof(used) );

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

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

		int sz = q.size();
		while( sz-- ){
			int x, y;
			tie(x, y) = q.front();
			q.pop();
			for(int i = 0 ; i < 4 ; i++){
				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;
					// 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]);
	}
	hive_bfs();
	for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++){
		if( a[i][j] == 'D' ){
			home = mp( i, j );
			a[i][j] = 'G';
		}
		if( a[i][j] == 'G' ){
			mecho = mp( i, j );
		}
	}

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

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

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:88: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:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
3.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5248 KB Output is correct
2 Incorrect 7 ms 5248 KB Output isn't correct
3 Correct 7 ms 5248 KB Output is correct
4 Incorrect 7 ms 5248 KB Output isn't correct
5 Incorrect 6 ms 5248 KB Output isn't correct
6 Incorrect 5 ms 5248 KB Output isn't correct
7 Incorrect 168 ms 6848 KB Output isn't correct
8 Incorrect 7 ms 5248 KB Output isn't correct
9 Incorrect 6 ms 5248 KB Output isn't correct
10 Incorrect 6 ms 5248 KB Output isn't correct
11 Incorrect 7 ms 5248 KB Output isn't correct
12 Incorrect 8 ms 5376 KB Output isn't correct
13 Incorrect 10 ms 5376 KB Output isn't correct
14 Incorrect 7 ms 5376 KB Output isn't correct
15 Incorrect 8 ms 5248 KB Output isn't correct
16 Incorrect 10 ms 5248 KB Output isn't correct
17 Incorrect 7 ms 5248 KB Output isn't correct
18 Incorrect 13 ms 5376 KB Output isn't correct
19 Incorrect 6 ms 5248 KB Output isn't correct
20 Incorrect 17 ms 5376 KB Output isn't correct
21 Incorrect 8 ms 5376 KB Output isn't correct
22 Incorrect 25 ms 5376 KB Output isn't correct
23 Incorrect 7 ms 5376 KB Output isn't correct
24 Incorrect 39 ms 5376 KB Output isn't correct
25 Incorrect 10 ms 5376 KB Output isn't correct
26 Incorrect 62 ms 5376 KB Output isn't correct
27 Incorrect 7 ms 5376 KB Output isn't correct
28 Incorrect 81 ms 5420 KB Output isn't correct
29 Incorrect 6 ms 5376 KB Output isn't correct
30 Incorrect 81 ms 5280 KB Output isn't correct
31 Incorrect 15 ms 5376 KB Output isn't correct
32 Incorrect 114 ms 5376 KB Output isn't correct
33 Incorrect 10 ms 5760 KB Output isn't correct
34 Runtime error 252 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Incorrect 21 ms 5760 KB Output isn't correct
36 Incorrect 790 ms 5852 KB Output isn't correct
37 Runtime error 303 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Incorrect 40 ms 5888 KB Output isn't correct
39 Incorrect 16 ms 5888 KB Output isn't correct
40 Runtime error 271 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Incorrect 42 ms 5888 KB Output isn't correct
42 Execution timed out 1078 ms 6016 KB Time limit exceeded
43 Runtime error 269 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Incorrect 52 ms 5988 KB Output isn't correct
45 Incorrect 17 ms 6144 KB Output isn't correct
46 Runtime error 330 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Incorrect 61 ms 6144 KB Output isn't correct
48 Execution timed out 1062 ms 6180 KB Time limit exceeded
49 Runtime error 247 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Incorrect 60 ms 6272 KB Output isn't correct
51 Incorrect 17 ms 6400 KB Output isn't correct
52 Runtime error 273 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Incorrect 91 ms 6264 KB Output isn't correct
54 Execution timed out 1062 ms 6528 KB Time limit exceeded
55 Runtime error 274 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Incorrect 105 ms 6648 KB Output isn't correct
57 Incorrect 27 ms 6616 KB Output isn't correct
58 Runtime error 284 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Incorrect 126 ms 6648 KB Output isn't correct
60 Execution timed out 1027 ms 6648 KB Time limit exceeded
61 Runtime error 314 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Incorrect 141 ms 6648 KB Output isn't correct
63 Execution timed out 1062 ms 6696 KB Time limit exceeded
64 Runtime error 248 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Execution timed out 1068 ms 6648 KB Time limit exceeded
66 Execution timed out 1066 ms 6696 KB Time limit exceeded
67 Execution timed out 1054 ms 6648 KB Time limit exceeded
68 Incorrect 364 ms 6776 KB Output isn't correct
69 Incorrect 899 ms 6980 KB Output isn't correct
70 Incorrect 596 ms 6904 KB Output isn't correct
71 Incorrect 556 ms 6904 KB Output isn't correct
72 Execution timed out 1065 ms 6776 KB Time limit exceeded
73 Execution timed out 1078 ms 6880 KB Time limit exceeded
74 Execution timed out 1068 ms 6808 KB Time limit exceeded
75 Execution timed out 1074 ms 6928 KB Time limit exceeded
76 Incorrect 918 ms 7008 KB Output isn't correct
77 Execution timed out 1062 ms 6752 KB Time limit exceeded
78 Incorrect 406 ms 6908 KB Output isn't correct
79 Execution timed out 1062 ms 6780 KB Time limit exceeded
80 Incorrect 981 ms 6896 KB Output isn't correct
81 Incorrect 819 ms 6912 KB Output isn't correct
82 Execution timed out 1064 ms 6780 KB Time limit exceeded
83 Incorrect 30 ms 6816 KB Output isn't correct
84 Incorrect 74 ms 6816 KB Output isn't correct
85 Incorrect 31 ms 6816 KB Output isn't correct
86 Incorrect 31 ms 6816 KB Output isn't correct
87 Incorrect 45 ms 6816 KB Output isn't correct
88 Incorrect 40 ms 6868 KB Output isn't correct
89 Incorrect 295 ms 7000 KB Output isn't correct
90 Incorrect 104 ms 6868 KB Output isn't correct
91 Incorrect 187 ms 6844 KB Output isn't correct
92 Incorrect 58 ms 6868 KB Output isn't correct