oj.uz

답안 #941729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941729 2024-03-09T11:05:00 Z RavenHead Mecho (IOI09_mecho) C++17
30 / 100
 202 ms 11604 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define EB emplace_back
#define all(x) std::begin(x), std::end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(long long i = a; i < (b); ++i)
#define endl '\n'
#define debarr(a, n) cerr << #a << " : ";for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << endl;
#define debmat(mat, row, col) cerr << #mat << " :\n";for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) cerr << mat[i][j] << " ";cerr << endl;}
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}

typedef long long lli;
typedef pair<lli, lli> ii;    typedef vector<lli> vi;
typedef vector<ii> vii;       typedef vector<vi> graph;
bool ckmax(auto &a, auto const& b) {return b > a ? a = b, 1 : 0;}
bool ckmin(auto &a, auto const& b) {return b < a ? a = b, 1 : 0;}

int const MOD = 1000000007;

void pre() {

}

void solve() {
	lli n, s;
	cin >> n >> s;
	vector<string> arr(n);
	rep(i, 0, n) {
		cin >> arr[i];
	}
	ii mecho, home;
	rep(i, 0, n)rep(j, 0, n) {
		if (arr[i][j] == 'M') {
			mecho = {i, j};
		}
		else if (arr[i][j] == 'D') {
			home = {i, j};
		}
	}

	// checks function
	auto checks = [&](lli xx, lli yy)->bool{
		if (xx >= 0 && xx < n && yy >= 0 && yy < n && (arr[xx][yy] == 'G' || arr[xx][yy] == 'D'))return true;
		return false;
	};

	int const dx[4] = { -1, 1, 0, 0};
	int const dy[4] = {0, 0, -1, 1};

	graph dis(n, vi(n, 1e9));
	queue<ii> q;
	rep(i, 0, n)rep(j, 0, n)if (arr[i][j] == 'H') {
		q.push({i, j});
		dis[i][j] = 0;
	}
	while (!q.empty()) {
		auto nn = q.front(); q.pop();
		rep(dir, 0, 4) {
			lli xx = nn.F + dx[dir];
			lli yy = nn.S + dy[dir];
			if (checks(xx, yy)) {
				if (dis[xx][yy] > dis[nn.F][nn.S] + 1) {
					dis[xx][yy] = dis[nn.F][nn.S] + 1;
					q.push({xx, yy});
				}
			}
		}
	}

	// check function
	auto check = [&](lli mid)->bool{
		graph d(n, vi(n, 1e9));
		d[mecho.F][mecho.S] = 0;
		q.push(mecho);
		while (!q.empty()) {
			auto nn = q.front(); q.pop();
			if (dis[nn.F][nn.S] < mid + (d[nn.F][nn.S] + s - 1) / s) {
				continue;
			}
			rep(dir, 0, 4) {
				lli xx = nn.F + dx[dir];
				lli yy = nn.S + dy[dir];
				if (xx >= 0 && xx < n && yy >= 0 && yy < n && (arr[xx][yy] == 'G' || arr[xx][yy] == 'D')) {
					if (d[xx][yy] > d[nn.F][nn.S] + 1) {
						d[xx][yy] = d[nn.F][nn.S] + 1;
						q.push({xx, yy});
					}
				}
			}
		}
		return mid + (d[home.F][home.S] + s - 1) / s <= dis[home.F][home.S];
	};

	lli low = 0;
	lli high = 1e9;
	lli ans = -1;
	while (low <= high) {
		lli mid = (high + low) / 2;
		if (check(mid)) {
			ans = mid;
			low = mid + 1;
		} else high = mid - 1;
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	pre();
	int T = 1;
	while (T--)
		solve();
	return 0;
}

Compilation message

mecho.cpp:27:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 | bool ckmax(auto &a, auto const& b) {return b > a ? a = b, 1 : 0;}
      |            ^~~~
mecho.cpp:27:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 | bool ckmax(auto &a, auto const& b) {return b > a ? a = b, 1 : 0;}
      |                     ^~~~
mecho.cpp:28:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 | bool ckmin(auto &a, auto const& b) {return b < a ? a = b, 1 : 0;}
      |            ^~~~
mecho.cpp:28:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 | bool ckmin(auto &a, auto const& b) {return b < a ? a = b, 1 : 0;}
      |                     ^~~~

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 124 ms 11372 KB Output isn't correct
8 Incorrect 0 ms 344 KB Output isn't correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Correct 1 ms 344 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 1 ms 344 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 0 ms 344 KB Output isn't correct
22 Correct 1 ms 348 KB Output is correct
23 Incorrect 0 ms 348 KB Output isn't correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Correct 0 ms 348 KB Output is correct
27 Incorrect 0 ms 348 KB Output isn't correct
28 Correct 1 ms 348 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Correct 1 ms 348 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Correct 1 ms 348 KB Output is correct
33 Incorrect 10 ms 2536 KB Output isn't correct
34 Correct 11 ms 2536 KB Output is correct
35 Correct 24 ms 2644 KB Output is correct
36 Incorrect 13 ms 3244 KB Output isn't correct
37 Correct 12 ms 3168 KB Output is correct
38 Correct 29 ms 3172 KB Output is correct
39 Incorrect 17 ms 3972 KB Output isn't correct
40 Correct 16 ms 3972 KB Output is correct
41 Correct 42 ms 3896 KB Output is correct
42 Incorrect 20 ms 4780 KB Output isn't correct
43 Correct 18 ms 4776 KB Output is correct
44 Correct 52 ms 4756 KB Output is correct
45 Incorrect 26 ms 5664 KB Output isn't correct
46 Correct 26 ms 6008 KB Output is correct
47 Correct 61 ms 5616 KB Output is correct
48 Incorrect 33 ms 6744 KB Output isn't correct
49 Correct 29 ms 6588 KB Output is correct
50 Correct 73 ms 6564 KB Output is correct
51 Incorrect 36 ms 7712 KB Output isn't correct
52 Correct 34 ms 7704 KB Output is correct
53 Correct 82 ms 7708 KB Output is correct
54 Incorrect 41 ms 8848 KB Output isn't correct
55 Correct 42 ms 8808 KB Output is correct
56 Correct 101 ms 8860 KB Output is correct
57 Incorrect 43 ms 10032 KB Output isn't correct
58 Correct 42 ms 10044 KB Output is correct
59 Correct 122 ms 10072 KB Output is correct
60 Incorrect 50 ms 11304 KB Output isn't correct
61 Correct 51 ms 11320 KB Output is correct
62 Correct 148 ms 11392 KB Output is correct
63 Correct 126 ms 11312 KB Output is correct
64 Correct 189 ms 11288 KB Output is correct
65 Correct 202 ms 11364 KB Output is correct
66 Incorrect 137 ms 11444 KB Output isn't correct
67 Correct 125 ms 11400 KB Output is correct
68 Correct 79 ms 11460 KB Output is correct
69 Correct 74 ms 11400 KB Output is correct
70 Correct 62 ms 11460 KB Output is correct
71 Correct 71 ms 11604 KB Output is correct
72 Incorrect 66 ms 11392 KB Output isn't correct
73 Incorrect 83 ms 11336 KB Output isn't correct
74 Correct 80 ms 11412 KB Output is correct
75 Correct 100 ms 11468 KB Output is correct
76 Correct 90 ms 11372 KB Output is correct
77 Correct 84 ms 11508 KB Output is correct
78 Correct 92 ms 11356 KB Output is correct
79 Correct 81 ms 11332 KB Output is correct
80 Correct 89 ms 11480 KB Output is correct
81 Correct 88 ms 11384 KB Output is correct
82 Correct 86 ms 11416 KB Output is correct
83 Correct 100 ms 11352 KB Output is correct
84 Correct 93 ms 11412 KB Output is correct
85 Correct 92 ms 11424 KB Output is correct
86 Correct 100 ms 11400 KB Output is correct
87 Correct 92 ms 11452 KB Output is correct
88 Correct 105 ms 11364 KB Output is correct
89 Correct 122 ms 11508 KB Output is correct
90 Correct 105 ms 11376 KB Output is correct
91 Correct 105 ms 11408 KB Output is correct
92 Correct 101 ms 11388 KB Output is correct