oj.uz

Submission #519414

# Submission time Handle Problem Language Result Execution time Memory
519414 2022-01-26T10:34:26 Z MODDI Mecho (IOI09_mecho) C++14
30 / 100
 216 ms 7004 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 = 1000;
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;
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;
	bool vis[801][801];
	memset(vis, false, sizeof(vis));
	vis[sx][sy] = 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] && dist[nx][ny] >= cur_minute){
				if(nx == ex && ny == ey){
					finished = true;
					break;
				}
				vis[nx][ny] = 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:35: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]
   35 |   for(int i = 0; i < current.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:96: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]
   96 |  for(int i = 0; i < hives.size(); i++)
      |                 ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4812 KB Output isn't correct
2 Incorrect 2 ms 4812 KB Output isn't correct
3 Incorrect 2 ms 4812 KB Output isn't correct
4 Incorrect 2 ms 4812 KB Output isn't correct
5 Correct 2 ms 4812 KB Output is correct
6 Incorrect 3 ms 4812 KB Output isn't correct
7 Incorrect 109 ms 6388 KB Output isn't correct
8 Incorrect 3 ms 4812 KB Output isn't correct
9 Correct 2 ms 4812 KB Output is correct
10 Correct 3 ms 4780 KB Output is correct
11 Correct 2 ms 4812 KB Output is correct
12 Incorrect 3 ms 4912 KB Output isn't correct
13 Incorrect 3 ms 4812 KB Output isn't correct
14 Correct 3 ms 4812 KB Output is correct
15 Incorrect 2 ms 4776 KB Output isn't correct
16 Correct 2 ms 4812 KB Output is correct
17 Incorrect 2 ms 4812 KB Output isn't correct
18 Correct 3 ms 4812 KB Output is correct
19 Incorrect 3 ms 4812 KB Output isn't correct
20 Correct 3 ms 4812 KB Output is correct
21 Incorrect 3 ms 4780 KB Output isn't correct
22 Correct 3 ms 4812 KB Output is correct
23 Incorrect 3 ms 4804 KB Output isn't correct
24 Correct 3 ms 4812 KB Output is correct
25 Incorrect 3 ms 4780 KB Output isn't correct
26 Correct 3 ms 4812 KB Output is correct
27 Incorrect 3 ms 4784 KB Output isn't correct
28 Correct 4 ms 4812 KB Output is correct
29 Incorrect 4 ms 4844 KB Output isn't correct
30 Correct 4 ms 4812 KB Output is correct
31 Incorrect 3 ms 4908 KB Output isn't correct
32 Correct 3 ms 4912 KB Output is correct
33 Incorrect 15 ms 5200 KB Output isn't correct
34 Incorrect 13 ms 5176 KB Output isn't correct
35 Correct 25 ms 5316 KB Output is correct
36 Incorrect 18 ms 5292 KB Output isn't correct
37 Incorrect 15 ms 5292 KB Output isn't correct
38 Correct 41 ms 5440 KB Output is correct
39 Incorrect 20 ms 5444 KB Output isn't correct
40 Incorrect 19 ms 5444 KB Output isn't correct
41 Correct 40 ms 5540 KB Output is correct
42 Incorrect 24 ms 5496 KB Output isn't correct
43 Incorrect 25 ms 5484 KB Output isn't correct
44 Correct 51 ms 5536 KB Output is correct
45 Incorrect 29 ms 5548 KB Output isn't correct
46 Incorrect 27 ms 5572 KB Output isn't correct
47 Correct 61 ms 5740 KB Output is correct
48 Incorrect 33 ms 5768 KB Output isn't correct
49 Incorrect 31 ms 5644 KB Output isn't correct
50 Correct 76 ms 5848 KB Output is correct
51 Incorrect 40 ms 5756 KB Output isn't correct
52 Incorrect 37 ms 5796 KB Output isn't correct
53 Correct 88 ms 5952 KB Output is correct
54 Incorrect 51 ms 5948 KB Output isn't correct
55 Incorrect 43 ms 5988 KB Output isn't correct
56 Correct 103 ms 6076 KB Output is correct
57 Incorrect 51 ms 5988 KB Output isn't correct
58 Incorrect 53 ms 6076 KB Output isn't correct
59 Correct 119 ms 6288 KB Output is correct
60 Incorrect 57 ms 6140 KB Output isn't correct
61 Incorrect 53 ms 6116 KB Output isn't correct
62 Correct 135 ms 6316 KB Output is correct
63 Correct 123 ms 6308 KB Output is correct
64 Correct 216 ms 6236 KB Output is correct
65 Correct 162 ms 6212 KB Output is correct
66 Incorrect 152 ms 6200 KB Output isn't correct
67 Correct 137 ms 6304 KB Output is correct
68 Correct 72 ms 6356 KB Output is correct
69 Correct 70 ms 6244 KB Output is correct
70 Correct 63 ms 6252 KB Output is correct
71 Correct 68 ms 6268 KB Output is correct
72 Incorrect 55 ms 6248 KB Output isn't correct
73 Incorrect 61 ms 6916 KB Output isn't correct
74 Correct 79 ms 6920 KB Output is correct
75 Correct 94 ms 6956 KB Output is correct
76 Correct 81 ms 6908 KB Output is correct
77 Correct 89 ms 7004 KB Output is correct
78 Correct 101 ms 6652 KB Output is correct
79 Correct 72 ms 6656 KB Output is correct
80 Correct 98 ms 6668 KB Output is correct
81 Correct 90 ms 6676 KB Output is correct
82 Correct 82 ms 6636 KB Output is correct
83 Correct 100 ms 6548 KB Output is correct
84 Correct 93 ms 6572 KB Output is correct
85 Correct 97 ms 6636 KB Output is correct
86 Correct 99 ms 6632 KB Output is correct
87 Correct 97 ms 6588 KB Output is correct
88 Correct 102 ms 6624 KB Output is correct
89 Correct 116 ms 6556 KB Output is correct
90 Correct 104 ms 6604 KB Output is correct
91 Correct 102 ms 6616 KB Output is correct
92 Correct 108 ms 6716 KB Output is correct