oj.uz

답안 #103684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103684 2019-04-02T04:23:25 Z turbat Mecho (IOI09_mecho) C++14
42 / 100
 805 ms 3976 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using pii = pair<int, int>;
using vi = vector <int>;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define ook order_of_key
#define fbo find_by_order
#define sq(x) (x) * (x)
#define N 805

int x, y, posx, posy, n, s;
int ax[4] = {0, 0, 1, -1};
int ay[4] = {1, -1, 0, 0}; 
string st[N];
queue <pii> que, q, bfs, mecho;
bool used[N][N], vis[N][N], pass[N][N];

bool check(int curx, int cury){
	if (curx < n && cury < n && curx >= 0 && cury >= 0 && !used[curx][cury]) return true;
	return false;
}

bool can(int time){;
	que = q;
	mecho.push(mp(x, y));
	memset(pass, 0, sizeof pass);
	pass[x][y] = 1;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++)
			used[i][j] = vis[i][j];
	while (time--){
		bfs = que;
		while(!que.empty()) que.pop();
		while (!bfs.empty()){
			pii pos = bfs.front();
			bfs.pop();
			for (int i = 0;i < 4;i++)
				if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T')
					que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
		} 
	}
	while (!used[posx][posy]){
		int tmp = s;
		while (tmp--){
			bfs = mecho;
			while (!mecho.empty()) mecho.pop();
			while (!bfs.empty()){
				pii pos = bfs.front();
				bfs.pop();
				if (pos.F == posx && pos.S == posy) return true;			
				if (!used[pos.F][pos.S])
					for (int i = 0;i < 4;i++)
						if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T'
							&& !pass[pos.F + ax[i]][pos.S + ay[i]])
							mecho.push(mp(pos.F + ax[i], pos.S + ay[i])), pass[pos.F + ax[i]][pos.S + ay[i]] = 1;
			}
		}
		bfs = que;
		while (!que.empty()) que.pop();
		while (!bfs.empty()){
			pii pos = bfs.front();
			bfs.pop();
			for (int i = 0;i < 4;i++)
				if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T')
					que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
		} 
	}
	return false;
}

int main (){
	cin >> n>> s;
	for (int i = 0;i < n;i++)
		cin >> st[i];
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++){
			if (st[i][j] == 'M') x = i, y = j;
			if (st[i][j] == 'D') posx = i, posy = j;
			if (st[i][j] == 'H') q.push(mp(i, j)), vis[i][j] = 1;
		}
	int l = 0, r = n * n;
	while (l != r){
		int mid = (l + r + 1) / 2;
		if (can(mid)) l = mid;
		else r = mid - 1;
	}
	if (can(l)) cout << l<< endl;
	else cout << -1 << endl;
}

Subtask #1
42.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Incorrect 3 ms 1024 KB Output isn't correct
3 Correct 3 ms 1024 KB Output is correct
4 Incorrect 3 ms 1024 KB Output isn't correct
5 Correct 3 ms 1024 KB Output is correct
6 Incorrect 2 ms 1024 KB Output isn't correct
7 Incorrect 376 ms 3096 KB Output isn't correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 1024 KB Output is correct
10 Correct 4 ms 996 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Incorrect 4 ms 1152 KB Output isn't correct
13 Correct 6 ms 1024 KB Output is correct
14 Correct 5 ms 1152 KB Output is correct
15 Correct 3 ms 1024 KB Output is correct
16 Correct 3 ms 1024 KB Output is correct
17 Correct 4 ms 1024 KB Output is correct
18 Correct 3 ms 1024 KB Output is correct
19 Correct 4 ms 1024 KB Output is correct
20 Correct 3 ms 1024 KB Output is correct
21 Correct 5 ms 1024 KB Output is correct
22 Correct 3 ms 1100 KB Output is correct
23 Correct 7 ms 1024 KB Output is correct
24 Correct 4 ms 1024 KB Output is correct
25 Correct 6 ms 1024 KB Output is correct
26 Correct 5 ms 1124 KB Output is correct
27 Correct 9 ms 1024 KB Output is correct
28 Correct 5 ms 1024 KB Output is correct
29 Correct 7 ms 1152 KB Output is correct
30 Correct 7 ms 1024 KB Output is correct
31 Correct 6 ms 1024 KB Output is correct
32 Correct 6 ms 1024 KB Output is correct
33 Correct 101 ms 1516 KB Output is correct
34 Correct 50 ms 1536 KB Output is correct
35 Incorrect 34 ms 1528 KB Output isn't correct
36 Correct 168 ms 1656 KB Output is correct
37 Correct 69 ms 1664 KB Output is correct
38 Incorrect 65 ms 1536 KB Output isn't correct
39 Correct 224 ms 1536 KB Output is correct
40 Correct 90 ms 1664 KB Output is correct
41 Incorrect 53 ms 1612 KB Output isn't correct
42 Correct 297 ms 1792 KB Output is correct
43 Correct 168 ms 2040 KB Output is correct
44 Incorrect 84 ms 1920 KB Output isn't correct
45 Correct 420 ms 1992 KB Output is correct
46 Correct 125 ms 2048 KB Output is correct
47 Incorrect 117 ms 2040 KB Output isn't correct
48 Correct 469 ms 2048 KB Output is correct
49 Correct 150 ms 2176 KB Output is correct
50 Correct 106 ms 2048 KB Output is correct
51 Correct 433 ms 2268 KB Output is correct
52 Correct 182 ms 2320 KB Output is correct
53 Incorrect 121 ms 2176 KB Output isn't correct
54 Correct 642 ms 2176 KB Output is correct
55 Correct 226 ms 2296 KB Output is correct
56 Incorrect 188 ms 2296 KB Output isn't correct
57 Correct 591 ms 2424 KB Output is correct
58 Correct 284 ms 2476 KB Output is correct
59 Incorrect 190 ms 2424 KB Output isn't correct
60 Correct 805 ms 2524 KB Output is correct
61 Correct 285 ms 2680 KB Output is correct
62 Incorrect 207 ms 2480 KB Output isn't correct
63 Correct 567 ms 2480 KB Output is correct
64 Correct 651 ms 2596 KB Output is correct
65 Correct 533 ms 2552 KB Output is correct
66 Correct 507 ms 2432 KB Output is correct
67 Correct 526 ms 2552 KB Output is correct
68 Correct 442 ms 3072 KB Output is correct
69 Correct 432 ms 3232 KB Output is correct
70 Correct 473 ms 3192 KB Output is correct
71 Correct 538 ms 3192 KB Output is correct
72 Correct 543 ms 3064 KB Output is correct
73 Correct 378 ms 3684 KB Output is correct
74 Incorrect 395 ms 3836 KB Output isn't correct
75 Incorrect 385 ms 3748 KB Output isn't correct
76 Incorrect 421 ms 3728 KB Output isn't correct
77 Correct 441 ms 3976 KB Output is correct
78 Incorrect 400 ms 3432 KB Output isn't correct
79 Correct 392 ms 3260 KB Output is correct
80 Incorrect 424 ms 3464 KB Output isn't correct
81 Incorrect 464 ms 3440 KB Output isn't correct
82 Incorrect 379 ms 3252 KB Output isn't correct
83 Incorrect 395 ms 3196 KB Output isn't correct
84 Correct 499 ms 3264 KB Output is correct
85 Incorrect 446 ms 3396 KB Output isn't correct
86 Incorrect 381 ms 3180 KB Output isn't correct
87 Incorrect 380 ms 3352 KB Output isn't correct
88 Incorrect 477 ms 3220 KB Output isn't correct
89 Correct 403 ms 3128 KB Output is correct
90 Incorrect 385 ms 3208 KB Output isn't correct
91 Correct 421 ms 3172 KB Output is correct
92 Incorrect 397 ms 3300 KB Output isn't correct