oj.uz

Submission #1016368

# Submission time Handle Problem Language Result Execution time Memory
1016368 2024-07-08T01:42:54 Z nrg_studio Mecho (IOI09_mecho) C++17
23 / 100
 82 ms 11536 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
#define FOR(i, a, b, s) for (int i = (a); i < (b); i += s)
#define F0R(i, a) for (int i = 0; i < (a); i++)

vector<vector<int>> g;
pii mecho, home;
int n, s;
pii d[4] = {{0,1},{0,-1},{1,0},{-1,0}};

bool check(int t) {
	vector<vector<int>> dist(n+2,vector<int>(n+2,INT_MAX));
	dist[mecho.f][mecho.s] = t*s;
	queue<pii> q; q.push(mecho);
	
	while (q.size()) {
		pii cur = q.front(); q.pop();
		if (dist[cur.f][cur.s]>=g[cur.f][cur.s]) {continue;}
		for (pii y : d) {
			if (dist[cur.f+y.f][cur.s+y.s]==INT_MAX) {
				dist[cur.f+y.f][cur.s+y.s] = dist[cur.f][cur.s]+1;
				q.push({cur.f+y.f,cur.s+y.s});
			}
		}
	} return (dist[home.f][home.s]!=INT_MAX);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> s;
	g = vector<vector<int>>(n+2,vector<int>(n+2,INT_MAX));
	char c; queue<pii> q;
	F0R(i,n) {
		F0R(j,n) {
			cin >> c;
			if (c=='M') {mecho = {i+1,j+1};}
			else if (c=='D') {home = {i+1,j+1};}
			else if (c=='H') {g[i+1][j+1]=0; q.push({i+1,j+1});}
			else if (c=='G') {g[i+1][j+1]=-1;}
			else if (c=='T') {g[i+1][j+1]=-2;}
		}
	}
	F0R(i,n) {g[0][i] = g[i][0] = g[n+1][i] = g[i][n+1] = -2;}
	while (q.size()) {
		pii x = q.front(); q.pop();
		for (pii y : d) {
			if (g[x.f+y.f][x.s+y.s]==-1) {
				g[x.f+y.f][x.s+y.s]=g[x.f][x.s]+s;
				q.push({x.f+y.f,x.s+y.s});
			}
		}
	} 
	int l = 0, h = 2*n, m = (l+h)/2, ans = -1;
	while (l <= h) {
		if (check(m)) {ans = m; l = m+1;}
		else {h = m-1;}
		m = (l+h)/2;
	} cout << ans << '\n';
}

Subtask #1
23.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Runtime error 0 ms 604 KB Execution killed with signal 11
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Runtime error 0 ms 348 KB Execution killed with signal 11
5 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 20 ms 11412 KB Execution killed with signal 11
8 Correct 0 ms 348 KB Output is correct
9 Runtime error 1 ms 600 KB Execution killed with signal 11
10 Runtime error 1 ms 600 KB Execution killed with signal 11
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Correct 0 ms 348 KB Output is correct
15 Runtime error 1 ms 348 KB Execution killed with signal 11
16 Incorrect 0 ms 348 KB Output isn't correct
17 Runtime error 1 ms 604 KB Execution killed with signal 11
18 Incorrect 0 ms 348 KB Output isn't correct
19 Runtime error 0 ms 604 KB Execution killed with signal 11
20 Incorrect 0 ms 460 KB Output isn't correct
21 Runtime error 0 ms 604 KB Execution killed with signal 11
22 Incorrect 1 ms 348 KB Output isn't correct
23 Runtime error 1 ms 604 KB Execution killed with signal 11
24 Incorrect 1 ms 348 KB Output isn't correct
25 Runtime error 1 ms 604 KB Execution killed with signal 11
26 Incorrect 1 ms 348 KB Output isn't correct
27 Runtime error 1 ms 604 KB Execution killed with signal 11
28 Incorrect 1 ms 348 KB Output isn't correct
29 Runtime error 1 ms 604 KB Execution killed with signal 11
30 Incorrect 1 ms 344 KB Output isn't correct
31 Runtime error 1 ms 464 KB Execution killed with signal 11
32 Incorrect 1 ms 460 KB Output isn't correct
33 Runtime error 3 ms 2612 KB Execution killed with signal 11
34 Incorrect 16 ms 1812 KB Output isn't correct
35 Runtime error 11 ms 2744 KB Execution killed with signal 11
36 Runtime error 4 ms 3288 KB Execution killed with signal 11
37 Incorrect 20 ms 1884 KB Output isn't correct
38 Runtime error 16 ms 3364 KB Execution killed with signal 11
39 Runtime error 5 ms 3932 KB Execution killed with signal 11
40 Incorrect 25 ms 2256 KB Output isn't correct
41 Runtime error 20 ms 3948 KB Execution killed with signal 11
42 Runtime error 7 ms 4696 KB Execution killed with signal 11
43 Incorrect 31 ms 2696 KB Output isn't correct
44 Runtime error 29 ms 4720 KB Execution killed with signal 11
45 Runtime error 8 ms 5720 KB Execution killed with signal 11
46 Incorrect 42 ms 3188 KB Output isn't correct
47 Runtime error 30 ms 5712 KB Execution killed with signal 11
48 Runtime error 9 ms 6748 KB Execution killed with signal 11
49 Incorrect 49 ms 3700 KB Output isn't correct
50 Runtime error 34 ms 6576 KB Execution killed with signal 11
51 Runtime error 10 ms 7772 KB Execution killed with signal 11
52 Incorrect 49 ms 4232 KB Output isn't correct
53 Runtime error 36 ms 7844 KB Execution killed with signal 11
54 Runtime error 12 ms 8792 KB Execution killed with signal 11
55 Incorrect 62 ms 4816 KB Output isn't correct
56 Runtime error 41 ms 8836 KB Execution killed with signal 11
57 Runtime error 13 ms 10076 KB Execution killed with signal 11
58 Incorrect 66 ms 5504 KB Output isn't correct
59 Runtime error 52 ms 10108 KB Execution killed with signal 11
60 Runtime error 15 ms 11292 KB Execution killed with signal 11
61 Incorrect 76 ms 6132 KB Output isn't correct
62 Runtime error 66 ms 11364 KB Execution killed with signal 11
63 Runtime error 74 ms 11364 KB Execution killed with signal 11
64 Runtime error 36 ms 11344 KB Execution killed with signal 11
65 Runtime error 41 ms 11448 KB Execution killed with signal 11
66 Runtime error 42 ms 11456 KB Execution killed with signal 11
67 Correct 82 ms 6164 KB Output is correct
68 Runtime error 41 ms 11536 KB Execution killed with signal 11
69 Runtime error 36 ms 11336 KB Execution killed with signal 11
70 Runtime error 29 ms 11488 KB Execution killed with signal 11
71 Runtime error 30 ms 11412 KB Execution killed with signal 11
72 Incorrect 50 ms 6192 KB Output isn't correct
73 Incorrect 44 ms 6204 KB Output isn't correct
74 Correct 35 ms 6168 KB Output is correct
75 Correct 43 ms 6160 KB Output is correct
76 Correct 38 ms 6212 KB Output is correct
77 Correct 41 ms 6204 KB Output is correct
78 Correct 48 ms 6172 KB Output is correct
79 Correct 34 ms 6216 KB Output is correct
80 Correct 37 ms 6200 KB Output is correct
81 Correct 42 ms 6212 KB Output is correct
82 Correct 37 ms 6188 KB Output is correct
83 Correct 45 ms 6172 KB Output is correct
84 Correct 42 ms 6212 KB Output is correct
85 Correct 41 ms 6148 KB Output is correct
86 Correct 46 ms 6176 KB Output is correct
87 Correct 46 ms 6212 KB Output is correct
88 Correct 49 ms 6152 KB Output is correct
89 Correct 49 ms 6184 KB Output is correct
90 Correct 50 ms 6064 KB Output is correct
91 Correct 50 ms 6196 KB Output is correct
92 Correct 47 ms 6200 KB Output is correct