답안 #1103071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103071	2024-10-19T22:40:19 Z	ef10	Mecho (IOI09_mecho)	C++17	53 / 100	119 ms	8440 KB

mecho

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int N,S;
string M[1001];
struct node {
	int hd;
	int md;
};
bool v[1001][1001];
node all[1001][1001];
pair<int,int> m;

bool work(int e) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			all[i][j].md = -1;
		}
	}

	queue<pair<int,int> > q;
	q.push(m);
	all[m.first][m.second].md = 0;
	if (all[m.first][m.second].hd != -1 && all[m.first][m.second].hd <= e) return false;
	while (!q.empty()) {
		auto c = q.front();
						//cout << "handling " << c.first << "/" << c.second << "/" << all[c.first][c.second].md << endl;
		int cost = all[c.first][c.second].md+1;
		q.pop();
			for (auto i : {-1,1}) {
				for (int j = 0; j <= 1; j++) {
					int ti = j ? c.first : c.first+i;
					int tj = j ? c.second+i : c.second;
					if (ti < 0 || ti >= N || tj < 0 || tj >= N) continue;
					//cout << "          " << ti << "/" << tj << " " << endl;
					if (M[ti][tj] == 'T') continue;
					if (all[ti][tj].md >= 0 && all[ti][tj].md <= cost) continue;
					if (all[ti][tj].hd >= 0 && all[ti][tj].hd <= cost/S+e) continue;
					if (M[ti][tj] == 'D') return true;
					//cout << "          " << ti << "/" << tj << " passed" << endl;
					all[ti][tj].md = cost;
						q.push(make_pair(ti,tj));
						//cout << "       add q " << ti << "/" << tj << "/" << cost << endl;
				}
			}
		/*for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << all[i][j].md << " ";
			}
			cout << endl;
		}*/
	}
	return false;
}

int solve() {
	int lo = 0, hi = 2*N;
		// if none of the values in the range work, return lo - 1
	lo--;
	while (lo < hi) {
		// find the middle of the current range (rounding up)
		int mid = lo + (hi - lo + 1) / 2;
		//cout << "mid: " << mid << ", " << lo << "/" << hi << endl;
		if (work(mid)) {
			//cout << " worked" << endl;
			// if mid works, then all numbers smaller than mid also work
			lo = mid;
		} else {
			//cout << " not work" << endl;
			// if mid does not work, greater values would not work either
			hi = mid - 1;
		}
	}
	return lo;
}

int main() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			all[i][j].hd = -1;
		}
	}
	queue<pair<int,int> > q;
	for (int i = 0; i < N; i++) {
		cin >> M[i];
		for (int j = 0; j < N; j++) {
			if (M[i][j] == 'H') {
				all[i][j].hd = 0;
				q.push(make_pair(i,j));
			} else if (M[i][j] == 'M') {
				m = make_pair(i,j);
			}
		}
	}
	while (!q.empty()) {
		auto c = q.front();
		int cost = all[c.first][c.second].hd+1;
		q.pop();
		for (auto i : {-1,1}) {
			for (int j = 0; j <= 1; j++) {
				int ti = j ? c.first : c.first+i;
				int tj = j ? c.second+i : c.second;
				if (ti < 0 || ti >= N || tj < 0 || tj >= N) continue;
				if (M[ti][tj]=='T' || M[ti][tj]=='D' || (all[ti][tj].hd!=-1 && all[ti][tj].hd<=cost)) continue;
				all[ti][tj].hd = cost;
				q.push(make_pair(ti,tj));
				//cout << "add " << ti << "/" << tj << endl;
			}
		}
	}
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << all[i][j].hd << " ";
		}
		cout << endl;
	}*/
	int r = solve();
	cout << r << endl;
	//cout << work(3) << endl;
}

Subtask #1

53.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	69 ms	7504 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Incorrect	1 ms	2384 KB	Output isn't correct
13	Correct	1 ms	2640 KB	Output is correct
14	Correct	1 ms	2384 KB	Output is correct
15	Incorrect	1 ms	336 KB	Output isn't correct
16	Incorrect	1 ms	336 KB	Output isn't correct
17	Incorrect	1 ms	2384 KB	Output isn't correct
18	Incorrect	1 ms	2384 KB	Output isn't correct
19	Incorrect	1 ms	2384 KB	Output isn't correct
20	Incorrect	1 ms	2384 KB	Output isn't correct
21	Incorrect	1 ms	2384 KB	Output isn't correct
22	Incorrect	1 ms	2384 KB	Output isn't correct
23	Incorrect	1 ms	2384 KB	Output isn't correct
24	Incorrect	1 ms	2384 KB	Output isn't correct
25	Incorrect	1 ms	2556 KB	Output isn't correct
26	Incorrect	1 ms	2384 KB	Output isn't correct
27	Incorrect	1 ms	2392 KB	Output isn't correct
28	Incorrect	1 ms	2384 KB	Output isn't correct
29	Incorrect	1 ms	2640 KB	Output isn't correct
30	Incorrect	1 ms	2640 KB	Output isn't correct
31	Incorrect	1 ms	2640 KB	Output isn't correct
32	Incorrect	1 ms	2640 KB	Output isn't correct
33	Incorrect	5 ms	4688 KB	Output isn't correct
34	Incorrect	5 ms	4944 KB	Output isn't correct
35	Correct	13 ms	4904 KB	Output is correct
36	Incorrect	6 ms	4688 KB	Output isn't correct
37	Incorrect	6 ms	4856 KB	Output isn't correct
38	Correct	18 ms	4932 KB	Output is correct
39	Incorrect	8 ms	4944 KB	Output isn't correct
40	Incorrect	7 ms	4944 KB	Output isn't correct
41	Correct	25 ms	4944 KB	Output is correct
42	Incorrect	11 ms	5236 KB	Output isn't correct
43	Incorrect	9 ms	5232 KB	Output isn't correct
44	Correct	29 ms	5200 KB	Output is correct
45	Incorrect	12 ms	7248 KB	Output isn't correct
46	Incorrect	11 ms	7504 KB	Output isn't correct
47	Correct	35 ms	7248 KB	Output is correct
48	Incorrect	13 ms	7248 KB	Output isn't correct
49	Incorrect	12 ms	7248 KB	Output isn't correct
50	Correct	42 ms	7732 KB	Output is correct
51	Incorrect	15 ms	7712 KB	Output isn't correct
52	Incorrect	14 ms	7248 KB	Output isn't correct
53	Correct	60 ms	7504 KB	Output is correct
54	Incorrect	17 ms	7248 KB	Output isn't correct
55	Incorrect	15 ms	7248 KB	Output isn't correct
56	Correct	59 ms	7760 KB	Output is correct
57	Incorrect	18 ms	7504 KB	Output isn't correct
58	Incorrect	19 ms	7504 KB	Output isn't correct
59	Correct	68 ms	8080 KB	Output is correct
60	Incorrect	22 ms	8016 KB	Output isn't correct
61	Incorrect	19 ms	7680 KB	Output isn't correct
62	Correct	76 ms	8180 KB	Output is correct
63	Correct	84 ms	7504 KB	Output is correct
64	Correct	119 ms	7516 KB	Output is correct
65	Correct	119 ms	7504 KB	Output is correct
66	Correct	91 ms	7504 KB	Output is correct
67	Correct	88 ms	7504 KB	Output is correct
68	Correct	47 ms	7600 KB	Output is correct
69	Correct	38 ms	7420 KB	Output is correct
70	Correct	37 ms	7504 KB	Output is correct
71	Correct	37 ms	8016 KB	Output is correct
72	Correct	30 ms	7504 KB	Output is correct
73	Correct	34 ms	7760 KB	Output is correct
74	Correct	43 ms	7928 KB	Output is correct
75	Correct	47 ms	8272 KB	Output is correct
76	Correct	59 ms	7760 KB	Output is correct
77	Correct	49 ms	7760 KB	Output is correct
78	Correct	54 ms	7776 KB	Output is correct
79	Correct	45 ms	8272 KB	Output is correct
80	Correct	52 ms	7760 KB	Output is correct
81	Correct	53 ms	7760 KB	Output is correct
82	Correct	46 ms	7772 KB	Output is correct
83	Correct	59 ms	7772 KB	Output is correct
84	Correct	57 ms	7768 KB	Output is correct
85	Correct	55 ms	7760 KB	Output is correct
86	Correct	59 ms	7760 KB	Output is correct
87	Correct	58 ms	8292 KB	Output is correct
88	Correct	66 ms	7504 KB	Output is correct
89	Correct	60 ms	8440 KB	Output is correct
90	Correct	63 ms	8240 KB	Output is correct
91	Correct	69 ms	7504 KB	Output is correct
92	Correct	57 ms	8016 KB	Output is correct