oj.uz

답안 #519432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519432 2022-01-26T10:54:58 Z MODDI Mecho (IOI09_mecho) C++14
27 / 100
 1000 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};
int counter = 0;
vector<pii> hives;
bool vis[800][800];
class state{
	public:
		int x;
		int y;
		int steps_made;
		int cur_minute;
		vector<vector<bool> > vis;
	
};
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;
	vector<vector<bool>> vis(n, vector<bool>(n, false));
	q.push({sx,sy,0,minutes+1, vis});
	bool finished = false;
	while(!q.empty()){
		counter++;
		state current = q.front(); q.pop();
		int x = current.x, y = current.y, steps_made = current.steps_made, cur_minute = current.cur_minute;
		vector<vector<bool>> vis = current.vis;
		//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(dist[nx][ny] == cur_minute && steps_made + 1 == s)
					continue;
				if(nx == ex && ny == ey){
					finished = true;
					break;
				}
				vis[nx][ny] = true;
				q.push({nx, ny, steps_made + 1, cur_minute,vis});
			}
		}
		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<<counter<<endl;
	cout<<solution<<endl;
}

Compilation message

mecho.cpp: In function 'void calculate_dist()':
mecho.cpp:39: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]
   39 |   for(int i = 0; i < current.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:103: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]
  103 |  for(int i = 0; i < hives.size(); i++)
      |                 ~~^~~~~~~~~~~~~~

Subtask #1
27.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2764 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Correct 2 ms 2736 KB Output is correct
4 Incorrect 1 ms 2764 KB Output isn't correct
5 Correct 2 ms 2736 KB Output is correct
6 Incorrect 10 ms 3248 KB Output isn't correct
7 Runtime error 272 ms 65540 KB Execution killed with signal 9
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2744 KB Output is correct
10 Correct 5 ms 2892 KB Output is correct
11 Correct 46 ms 6960 KB Output is correct
12 Incorrect 12 ms 2764 KB Output isn't correct
13 Runtime error 630 ms 65540 KB Execution killed with signal 9
14 Runtime error 668 ms 65536 KB Execution killed with signal 9
15 Correct 2 ms 2764 KB Output is correct
16 Correct 2 ms 2736 KB Output is correct
17 Correct 3 ms 2764 KB Output is correct
18 Correct 7 ms 2732 KB Output is correct
19 Correct 3 ms 2764 KB Output is correct
20 Correct 8 ms 2764 KB Output is correct
21 Correct 5 ms 2896 KB Output is correct
22 Correct 18 ms 2872 KB Output is correct
23 Correct 4 ms 2868 KB Output is correct
24 Correct 38 ms 2892 KB Output is correct
25 Correct 11 ms 2900 KB Output is correct
26 Correct 78 ms 2892 KB Output is correct
27 Correct 4 ms 2876 KB Output is correct
28 Correct 21 ms 2872 KB Output is correct
29 Correct 3 ms 2892 KB Output is correct
30 Correct 26 ms 2892 KB Output is correct
31 Correct 5 ms 2892 KB Output is correct
32 Correct 36 ms 2892 KB Output is correct
33 Incorrect 22 ms 3392 KB Output isn't correct
34 Execution timed out 1055 ms 3544 KB Time limit exceeded
35 Execution timed out 1073 ms 5440 KB Time limit exceeded
36 Incorrect 23 ms 3520 KB Output isn't correct
37 Execution timed out 1069 ms 3512 KB Time limit exceeded
38 Execution timed out 1045 ms 6192 KB Time limit exceeded
39 Incorrect 25 ms 3660 KB Output isn't correct
40 Execution timed out 1090 ms 3784 KB Time limit exceeded
41 Execution timed out 1073 ms 7932 KB Time limit exceeded
42 Incorrect 45 ms 3804 KB Output isn't correct
43 Execution timed out 1072 ms 3852 KB Time limit exceeded
44 Execution timed out 1066 ms 6836 KB Time limit exceeded
45 Incorrect 46 ms 3876 KB Output isn't correct
46 Execution timed out 1090 ms 4160 KB Time limit exceeded
47 Execution timed out 1077 ms 7724 KB Time limit exceeded
48 Incorrect 49 ms 4148 KB Output isn't correct
49 Execution timed out 1076 ms 4304 KB Time limit exceeded
50 Execution timed out 1094 ms 9576 KB Time limit exceeded
51 Incorrect 49 ms 4324 KB Output isn't correct
52 Execution timed out 1091 ms 4584 KB Time limit exceeded
53 Execution timed out 1082 ms 9328 KB Time limit exceeded
54 Incorrect 75 ms 4488 KB Output isn't correct
55 Execution timed out 1088 ms 4592 KB Time limit exceeded
56 Execution timed out 1092 ms 7484 KB Time limit exceeded
57 Incorrect 81 ms 4708 KB Output isn't correct
58 Execution timed out 1097 ms 5048 KB Time limit exceeded
59 Execution timed out 1085 ms 9036 KB Time limit exceeded
60 Incorrect 78 ms 4848 KB Output isn't correct
61 Execution timed out 1088 ms 5072 KB Time limit exceeded
62 Execution timed out 1076 ms 10304 KB Time limit exceeded
63 Execution timed out 1063 ms 8644 KB Time limit exceeded
64 Execution timed out 1070 ms 7288 KB Time limit exceeded
65 Execution timed out 1090 ms 7712 KB Time limit exceeded
66 Execution timed out 1093 ms 9052 KB Time limit exceeded
67 Execution timed out 1096 ms 8752 KB Time limit exceeded
68 Execution timed out 1095 ms 7372 KB Time limit exceeded
69 Execution timed out 1081 ms 7328 KB Time limit exceeded
70 Execution timed out 1098 ms 7376 KB Time limit exceeded
71 Execution timed out 1094 ms 7512 KB Time limit exceeded
72 Execution timed out 1095 ms 17276 KB Time limit exceeded
73 Runtime error 261 ms 65540 KB Execution killed with signal 9
74 Runtime error 252 ms 65540 KB Execution killed with signal 9
75 Runtime error 254 ms 65540 KB Execution killed with signal 9
76 Runtime error 257 ms 65540 KB Execution killed with signal 9
77 Runtime error 258 ms 65540 KB Execution killed with signal 9
78 Runtime error 256 ms 65540 KB Execution killed with signal 9
79 Runtime error 263 ms 65540 KB Execution killed with signal 9
80 Runtime error 256 ms 65540 KB Execution killed with signal 9
81 Runtime error 248 ms 65540 KB Execution killed with signal 9
82 Runtime error 256 ms 65540 KB Execution killed with signal 9
83 Runtime error 252 ms 65540 KB Execution killed with signal 9
84 Runtime error 251 ms 65540 KB Execution killed with signal 9
85 Runtime error 540 ms 65540 KB Execution killed with signal 9
86 Runtime error 252 ms 65540 KB Execution killed with signal 9
87 Runtime error 259 ms 65540 KB Execution killed with signal 9
88 Runtime error 246 ms 65540 KB Execution killed with signal 9
89 Runtime error 250 ms 65540 KB Execution killed with signal 9
90 Runtime error 253 ms 65540 KB Execution killed with signal 9
91 Runtime error 247 ms 65540 KB Execution killed with signal 9
92 Runtime error 246 ms 65540 KB Execution killed with signal 9