oj.uz

Submission #519421

# Submission time Handle Problem Language Result Execution time Memory
519421 2022-01-26T10:44:48 Z MODDI Mecho (IOI09_mecho) C++14
0 / 100
 89 ms 65540 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, s,sx, sy, ex, ey;
const int Nmax = 801;
char mat[Nmax][Nmax];
int dist[Nmax][Nmax];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pii> hives;
bool vis[800][800][200];
class state{
	public:
		int x;
		int y;
		int steps_made;
		int cur_minute;
};
bool in_range(int i, int j){
	if(i >= 0 && j >= 0 && i < n && j < n)
		return true;
	return false;
}
void calculate_dist(){
	queue<vector<pii> > q;
	q.push(hives);
	while(!q.empty()){
		vector<pii> current = q.front(); q.pop();
		vector<pii> next_current;
		for(int i = 0; i < current.size(); i++){
			int x = current[i].first, y = current[i].second;
			for(int dir = 0; dir < 4; dir++){
				int nx = x + dx[dir], ny = y + dy[dir];
				if(in_range(nx, ny) && mat[nx][ny] != 'T' && dist[nx][ny] == -1){
					dist[nx][ny] = 1 + dist[x][y];
					next_current.pb(mp(nx,ny));
				}
			}
		}
		if(next_current.size() > 0)
			q.push(next_current);
	}
}
bool solve(int minutes){
	queue<state> q;
	q.push({sx,sy,0,minutes+1});
	bool finished = false;
	
	memset(vis, false, sizeof(vis));
	vis[sx][sy][minutes] = true;
	while(!q.empty()){
		state current = q.front(); q.pop();
		int x = current.x, y = current.y, steps_made = current.steps_made, cur_minute = current.cur_minute;
		//cout<<x<<" "<<y<<" "<<steps_made<<" "<<cur_minute<<endl;
		if(steps_made == s){
			steps_made = 0;
			cur_minute++;
		}
			
		for(int dir = 0; dir < 4; dir++){
			int nx = x + dx[dir], ny = y + dy[dir];
			//cout<<dist[nx][ny]<<" "<<cur_minute<<endl;
			if(in_range(nx,ny) && mat[nx][ny] != 'T' &&  !vis[nx][ny][cur_minute] && dist[nx][ny] >= cur_minute){
				if(dist[nx][ny] == cur_minute && steps_made + 1 == s)
					continue;
				if(nx == ex && ny == ey){
					finished = true;
					break;
				}
				vis[nx][ny][cur_minute] = true;
				q.push({nx, ny, steps_made + 1, cur_minute});
			}
		}
		if(finished)
			break;
	}
return finished;
}
int main(){
	cin>>n>>s;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin>>mat[i][j];
			if(mat[i][j] == 'M')
				sx = i, sy = j;
			if(mat[i][j] == 'D')
				ex = i, ey = j;
			if(mat[i][j] == 'H')
				hives.pb(mp(i,j));
		}
	}
	memset(dist, -1, sizeof(dist));
	for(int i = 0; i < hives.size(); i++)
		dist[hives[i].first][hives[i].second] = 0;
		
	calculate_dist(); 
	int l = 0, r = 10000, solution=-1;
	while(l <= r){
		int mid = (l + r) / 2;
		bool sol = solve(mid);
		if(sol){
			solution = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout<<solution<<endl;
}

Compilation message

mecho.cpp: In function 'void calculate_dist()':
mecho.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i = 0; i < current.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i = 0; i < hives.size(); i++)
      |                 ~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 65540 KB Execution killed with signal 9
2 Runtime error 30 ms 65540 KB Execution killed with signal 9
3 Runtime error 28 ms 65540 KB Execution killed with signal 9
4 Runtime error 27 ms 65540 KB Execution killed with signal 9
5 Runtime error 29 ms 65540 KB Execution killed with signal 9
6 Runtime error 26 ms 65540 KB Execution killed with signal 9
7 Runtime error 74 ms 65540 KB Execution killed with signal 9
8 Runtime error 32 ms 65540 KB Execution killed with signal 9
9 Runtime error 34 ms 65540 KB Execution killed with signal 9
10 Runtime error 31 ms 65540 KB Execution killed with signal 9
11 Runtime error 29 ms 65540 KB Execution killed with signal 9
12 Runtime error 30 ms 65540 KB Execution killed with signal 9
13 Runtime error 31 ms 65540 KB Execution killed with signal 9
14 Runtime error 29 ms 65540 KB Execution killed with signal 9
15 Runtime error 30 ms 65536 KB Execution killed with signal 9
16 Runtime error 30 ms 65540 KB Execution killed with signal 9
17 Runtime error 28 ms 65540 KB Execution killed with signal 9
18 Runtime error 37 ms 65540 KB Execution killed with signal 9
19 Runtime error 30 ms 65540 KB Execution killed with signal 9
20 Runtime error 32 ms 65540 KB Execution killed with signal 9
21 Runtime error 29 ms 65540 KB Execution killed with signal 9
22 Runtime error 29 ms 65540 KB Execution killed with signal 9
23 Runtime error 32 ms 65540 KB Execution killed with signal 9
24 Runtime error 28 ms 65540 KB Execution killed with signal 9
25 Runtime error 29 ms 65540 KB Execution killed with signal 9
26 Runtime error 30 ms 65540 KB Execution killed with signal 9
27 Runtime error 29 ms 65540 KB Execution killed with signal 9
28 Runtime error 30 ms 65540 KB Execution killed with signal 9
29 Runtime error 33 ms 65540 KB Execution killed with signal 9
30 Runtime error 30 ms 65540 KB Execution killed with signal 9
31 Runtime error 30 ms 65540 KB Execution killed with signal 9
32 Runtime error 30 ms 65540 KB Execution killed with signal 9
33 Runtime error 42 ms 65540 KB Execution killed with signal 9
34 Runtime error 39 ms 65540 KB Execution killed with signal 9
35 Runtime error 38 ms 65540 KB Execution killed with signal 9
36 Runtime error 47 ms 65540 KB Execution killed with signal 9
37 Runtime error 41 ms 65540 KB Execution killed with signal 9
38 Runtime error 42 ms 65540 KB Execution killed with signal 9
39 Runtime error 47 ms 65540 KB Execution killed with signal 9
40 Runtime error 47 ms 65540 KB Execution killed with signal 9
41 Runtime error 45 ms 65540 KB Execution killed with signal 9
42 Runtime error 50 ms 65540 KB Execution killed with signal 9
43 Runtime error 47 ms 65540 KB Execution killed with signal 9
44 Runtime error 47 ms 65540 KB Execution killed with signal 9
45 Runtime error 61 ms 65540 KB Execution killed with signal 9
46 Runtime error 54 ms 65540 KB Execution killed with signal 9
47 Runtime error 49 ms 65540 KB Execution killed with signal 9
48 Runtime error 61 ms 65540 KB Execution killed with signal 9
49 Runtime error 60 ms 65540 KB Execution killed with signal 9
50 Runtime error 53 ms 65540 KB Execution killed with signal 9
51 Runtime error 65 ms 65540 KB Execution killed with signal 9
52 Runtime error 62 ms 65540 KB Execution killed with signal 9
53 Runtime error 56 ms 65540 KB Execution killed with signal 9
54 Runtime error 71 ms 65540 KB Execution killed with signal 9
55 Runtime error 70 ms 65540 KB Execution killed with signal 9
56 Runtime error 61 ms 65540 KB Execution killed with signal 9
57 Runtime error 83 ms 65540 KB Execution killed with signal 9
58 Runtime error 75 ms 65540 KB Execution killed with signal 9
59 Runtime error 66 ms 65540 KB Execution killed with signal 9
60 Runtime error 85 ms 65540 KB Execution killed with signal 9
61 Runtime error 81 ms 65540 KB Execution killed with signal 9
62 Runtime error 73 ms 65540 KB Execution killed with signal 9
63 Runtime error 79 ms 65540 KB Execution killed with signal 9
64 Runtime error 76 ms 65540 KB Execution killed with signal 9
65 Runtime error 75 ms 65540 KB Execution killed with signal 9
66 Runtime error 74 ms 65540 KB Execution killed with signal 9
67 Runtime error 75 ms 65540 KB Execution killed with signal 9
68 Runtime error 79 ms 65540 KB Execution killed with signal 9
69 Runtime error 77 ms 65540 KB Execution killed with signal 9
70 Runtime error 78 ms 65540 KB Execution killed with signal 9
71 Runtime error 76 ms 65540 KB Execution killed with signal 9
72 Runtime error 78 ms 65540 KB Execution killed with signal 9
73 Runtime error 74 ms 65540 KB Execution killed with signal 9
74 Runtime error 86 ms 65540 KB Execution killed with signal 9
75 Runtime error 78 ms 65540 KB Execution killed with signal 9
76 Runtime error 77 ms 65540 KB Execution killed with signal 9
77 Runtime error 73 ms 65540 KB Execution killed with signal 9
78 Runtime error 80 ms 65536 KB Execution killed with signal 9
79 Runtime error 77 ms 65540 KB Execution killed with signal 9
80 Runtime error 88 ms 65540 KB Execution killed with signal 9
81 Runtime error 82 ms 65540 KB Execution killed with signal 9
82 Runtime error 79 ms 65540 KB Execution killed with signal 9
83 Runtime error 83 ms 65540 KB Execution killed with signal 9
84 Runtime error 75 ms 65540 KB Execution killed with signal 9
85 Runtime error 74 ms 65540 KB Execution killed with signal 9
86 Runtime error 73 ms 65540 KB Execution killed with signal 9
87 Runtime error 89 ms 65540 KB Execution killed with signal 9
88 Runtime error 74 ms 65540 KB Execution killed with signal 9
89 Runtime error 74 ms 65540 KB Execution killed with signal 9
90 Runtime error 74 ms 65540 KB Execution killed with signal 9
91 Runtime error 81 ms 65540 KB Execution killed with signal 9
92 Runtime error 73 ms 65540 KB Execution killed with signal 9