oj.uz

Submission #103671

# Submission time Handle Problem Language Result Execution time Memory
103671 2019-04-02T03:54:38 Z tugushka Mecho (IOI09_mecho) C++14
1 / 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
1.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5248 KB Output isn't correct
2 Correct 6 ms 5248 KB Output is correct
3 Incorrect 6 ms 5248 KB Output isn't correct
4 Incorrect 6 ms 5340 KB Output isn't correct
5 Incorrect 7 ms 5248 KB Output isn't correct
6 Incorrect 6 ms 5248 KB Output isn't correct
7 Incorrect 179 ms 6232 KB Output isn't correct
8 Incorrect 6 ms 5248 KB Output isn't correct
9 Incorrect 7 ms 5248 KB Output isn't correct
10 Incorrect 7 ms 5248 KB Output isn't correct
11 Incorrect 7 ms 5220 KB Output isn't correct
12 Incorrect 6 ms 5376 KB Output isn't correct
13 Incorrect 9 ms 5248 KB Output isn't correct
14 Incorrect 6 ms 5376 KB Output isn't correct
15 Incorrect 6 ms 5248 KB Output isn't correct
16 Incorrect 10 ms 5248 KB Output isn't correct
17 Incorrect 5 ms 5348 KB Output isn't correct
18 Incorrect 13 ms 5248 KB Output isn't correct
19 Incorrect 5 ms 5248 KB Output isn't correct
20 Incorrect 15 ms 5248 KB Output isn't correct
21 Incorrect 10 ms 5348 KB Output isn't correct
22 Incorrect 30 ms 5248 KB Output isn't correct
23 Incorrect 6 ms 5248 KB Output isn't correct
24 Incorrect 40 ms 5248 KB Output isn't correct
25 Incorrect 13 ms 5376 KB Output isn't correct
26 Incorrect 63 ms 5248 KB Output isn't correct
27 Incorrect 7 ms 5376 KB Output isn't correct
28 Incorrect 75 ms 5368 KB Output isn't correct
29 Incorrect 8 ms 5376 KB Output isn't correct
30 Incorrect 105 ms 5468 KB Output isn't correct
31 Incorrect 19 ms 5376 KB Output isn't correct
32 Incorrect 108 ms 5496 KB Output isn't correct
33 Incorrect 13 ms 5632 KB Output isn't correct
34 Runtime error 284 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Incorrect 30 ms 5632 KB Output isn't correct
36 Incorrect 943 ms 5692 KB Output isn't correct
37 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Incorrect 47 ms 5632 KB Output isn't correct
39 Incorrect 17 ms 5760 KB Output isn't correct
40 Runtime error 307 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Incorrect 50 ms 5760 KB Output isn't correct
42 Execution timed out 1072 ms 5760 KB Time limit exceeded
43 Runtime error 258 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Incorrect 41 ms 5760 KB Output isn't correct
45 Incorrect 18 ms 5880 KB Output isn't correct
46 Runtime error 254 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Incorrect 62 ms 6012 KB Output isn't correct
48 Execution timed out 1065 ms 5888 KB Time limit exceeded
49 Runtime error 251 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Incorrect 75 ms 5888 KB Output isn't correct
51 Incorrect 30 ms 5888 KB Output isn't correct
52 Runtime error 272 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Incorrect 87 ms 5880 KB Output isn't correct
54 Execution timed out 1078 ms 5888 KB Time limit exceeded
55 Runtime error 278 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Incorrect 123 ms 5888 KB Output isn't correct
57 Incorrect 32 ms 6016 KB Output isn't correct
58 Runtime error 301 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Incorrect 137 ms 6136 KB Output isn't correct
60 Execution timed out 1063 ms 6008 KB Time limit exceeded
61 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Incorrect 178 ms 6144 KB Output isn't correct
63 Execution timed out 1073 ms 6008 KB Time limit exceeded
64 Runtime error 255 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Execution timed out 1062 ms 6008 KB Time limit exceeded
66 Execution timed out 1073 ms 6008 KB Time limit exceeded
67 Execution timed out 1057 ms 6008 KB Time limit exceeded
68 Incorrect 379 ms 6264 KB Output isn't correct
69 Incorrect 870 ms 6136 KB Output isn't correct
70 Incorrect 551 ms 6264 KB Output isn't correct
71 Incorrect 464 ms 6016 KB Output isn't correct
72 Execution timed out 1058 ms 6136 KB Time limit exceeded
73 Execution timed out 1093 ms 6272 KB Time limit exceeded
74 Execution timed out 1054 ms 6240 KB Time limit exceeded
75 Execution timed out 1059 ms 6240 KB Time limit exceeded
76 Execution timed out 1048 ms 6240 KB Time limit exceeded
77 Execution timed out 1058 ms 6244 KB Time limit exceeded
78 Incorrect 467 ms 6012 KB Output isn't correct
79 Execution timed out 1068 ms 6140 KB Time limit exceeded
80 Incorrect 853 ms 6268 KB Output isn't correct
81 Incorrect 689 ms 6252 KB Output isn't correct
82 Execution timed out 1025 ms 6252 KB Time limit exceeded
83 Incorrect 29 ms 6184 KB Output isn't correct
84 Incorrect 103 ms 6148 KB Output isn't correct
85 Incorrect 37 ms 6348 KB Output isn't correct
86 Incorrect 28 ms 6160 KB Output isn't correct
87 Incorrect 35 ms 6176 KB Output isn't correct
88 Incorrect 29 ms 6228 KB Output isn't correct
89 Incorrect 262 ms 6368 KB Output isn't correct
90 Incorrect 106 ms 6100 KB Output isn't correct
91 Incorrect 166 ms 6260 KB Output isn't correct
92 Incorrect 50 ms 6228 KB Output isn't correct