oj.uz

Submission #476427

# Submission time Handle Problem Language Result Execution time Memory
476427 2021-09-26T17:59:41 Z Morley Mecho (IOI09_mecho) C++14
22 / 100
 410 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvpi = vector<vector<pair<int,int>>>;
using vvb = vector<vector<bool>>;
using str = string;
using pi= pair<int,int>;
using pll = pair<ll,ll>;
using vpi = vector<pi>;
using ti = tuple<int,int,int>;
using vti = vector<ti>;

#define pb push_back
#define rs resize
#define mp make_pair
#define FOR(x,y,z) for(int x=y; x<z; x++)
#define F0R(x,z) for(int x=0; x<z; x++)
#define all(a) a.begin() , a.end()

ll mx = 1000000000000000000;
int inf = 2000000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

	int n,s; cin >> n >> s;
	vector<str> F(n);
	for(int i=0;i<n;i++) cin >> F[i];
	vvi hd(n,vi(n,inf));
	queue<ti> Q;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(F[i][j]=='H') Q.push({i,j,0});
	while(!Q.empty()) {
		ti cur=Q.front(); Q.pop();
		int i=get<0>(cur),j=get<1>(cur),d=get<2>(cur);
		//cout << i << j << d << "\n";
		if(d>=hd[i][j]) continue;
		hd[i][j]=d;
		if(i>0 && hd[i-1][j]==inf && (F[i-1][j]=='G' || F[i-1][j]=='M')) Q.push({i-1,j,d+1});
		if(i<n-1 && hd[i+1][j]==inf && (F[i+1][j]=='G' || F[i+1][j]=='M')) Q.push({i+1,j,d+1});
		if(j>0 && hd[i][j-1]==inf && (F[i][j-1]=='G' || F[i][j-1]=='M')) Q.push({i,j-1,d+1});
		if(j<n-1 && hd[i][j+1]==inf && (F[i][j+1]=='G' || F[i][j+1]=='M')) Q.push({i,j+1,d+1});
	}
	//for(int i=0;i<n;i++) {for(int j=0;j<n;j++) if(hd[i][j]<inf) cout << hd[i][j]; else cout << "T"; cout << "\n";}
	int lob=-1,upb=2*n;
	while(lob<upb) {
		int tst=(lob+upb+1)/2;
		queue<ti> Qp;
		for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(F[i][j]=='M') Qp.push({i,j,0});
		bool good=false; vvb vis(n,vb(n,false));
		while(!Qp.empty()) {
			ti cur=Qp.front(); Qp.pop();
			int i=get<0>(cur),j=get<1>(cur),d=get<2>(cur);
			//cout << i << j << d << " ";
			vis[i][j]=true;
			if(F[i][j]=='D') {good=true; break;}
			if(tst+d/s>=hd[i][j]) continue;
			if(i>0 && !vis[i-1][j] && (F[i-1][j]=='G' || F[i-1][j]=='D')) Qp.push({i-1,j,d+1});
			if(i<n-1 && !vis[i+1][j] && (F[i+1][j]=='G' || F[i+1][j]=='D')) Qp.push({i+1,j,d+1});
			if(j>0 && !vis[i][j-1] && (F[i][j-1]=='G' || F[i][j-1]=='D')) Qp.push({i,j-1,d+1});
			if(j<n-1 && !vis[i][j+1] && (F[i][j+1]=='G' || F[i][j+1]=='D')) Qp.push({i,j+1,d+1});
		}
		if(!good) upb=tst-1;
		else lob=tst;
	}
	cout << upb;

	return 0;
}

Subtask #1
22.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Runtime error 210 ms 65540 KB Execution killed with signal 9
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Runtime error 298 ms 65540 KB Execution killed with signal 9
14 Runtime error 172 ms 65540 KB Execution killed with signal 9
15 Incorrect 0 ms 204 KB Output isn't correct
16 Incorrect 0 ms 204 KB Output isn't correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Incorrect 1 ms 204 KB Output isn't correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Incorrect 0 ms 204 KB Output isn't correct
21 Incorrect 0 ms 204 KB Output isn't correct
22 Incorrect 1 ms 204 KB Output isn't correct
23 Incorrect 0 ms 204 KB Output isn't correct
24 Incorrect 1 ms 332 KB Output isn't correct
25 Incorrect 1 ms 332 KB Output isn't correct
26 Incorrect 1 ms 332 KB Output isn't correct
27 Incorrect 1 ms 332 KB Output isn't correct
28 Incorrect 1 ms 332 KB Output isn't correct
29 Incorrect 1 ms 332 KB Output isn't correct
30 Incorrect 1 ms 332 KB Output isn't correct
31 Incorrect 1 ms 332 KB Output isn't correct
32 Incorrect 1 ms 332 KB Output isn't correct
33 Incorrect 6 ms 972 KB Output isn't correct
34 Incorrect 4 ms 972 KB Output isn't correct
35 Runtime error 223 ms 65540 KB Execution killed with signal 9
36 Incorrect 4 ms 1100 KB Output isn't correct
37 Incorrect 4 ms 1100 KB Output isn't correct
38 Runtime error 206 ms 65540 KB Execution killed with signal 9
39 Incorrect 5 ms 1356 KB Output isn't correct
40 Incorrect 6 ms 1356 KB Output isn't correct
41 Runtime error 206 ms 65540 KB Execution killed with signal 9
42 Incorrect 7 ms 1612 KB Output isn't correct
43 Incorrect 7 ms 1612 KB Output isn't correct
44 Runtime error 210 ms 65540 KB Execution killed with signal 9
45 Incorrect 9 ms 1868 KB Output isn't correct
46 Incorrect 9 ms 1868 KB Output isn't correct
47 Runtime error 192 ms 65540 KB Execution killed with signal 9
48 Incorrect 10 ms 2144 KB Output isn't correct
49 Incorrect 10 ms 2144 KB Output isn't correct
50 Runtime error 208 ms 65540 KB Execution killed with signal 9
51 Incorrect 11 ms 2508 KB Output isn't correct
52 Incorrect 13 ms 2456 KB Output isn't correct
53 Runtime error 188 ms 65540 KB Execution killed with signal 9
54 Incorrect 20 ms 2764 KB Output isn't correct
55 Incorrect 14 ms 2764 KB Output isn't correct
56 Runtime error 269 ms 65540 KB Execution killed with signal 9
57 Incorrect 15 ms 3152 KB Output isn't correct
58 Incorrect 16 ms 3264 KB Output isn't correct
59 Runtime error 219 ms 65540 KB Execution killed with signal 9
60 Incorrect 19 ms 3548 KB Output isn't correct
61 Incorrect 19 ms 3660 KB Output isn't correct
62 Runtime error 222 ms 65540 KB Execution killed with signal 9
63 Correct 122 ms 3648 KB Output is correct
64 Correct 151 ms 3552 KB Output is correct
65 Correct 158 ms 3672 KB Output is correct
66 Correct 121 ms 3540 KB Output is correct
67 Correct 117 ms 3660 KB Output is correct
68 Correct 49 ms 3596 KB Output is correct
69 Correct 45 ms 3572 KB Output is correct
70 Correct 39 ms 3644 KB Output is correct
71 Correct 47 ms 3648 KB Output is correct
72 Correct 42 ms 3652 KB Output is correct
73 Runtime error 221 ms 65540 KB Execution killed with signal 9
74 Runtime error 214 ms 65540 KB Execution killed with signal 9
75 Runtime error 238 ms 65540 KB Execution killed with signal 9
76 Runtime error 269 ms 65540 KB Execution killed with signal 9
77 Runtime error 206 ms 65540 KB Execution killed with signal 9
78 Runtime error 410 ms 65540 KB Execution killed with signal 9
79 Runtime error 207 ms 65540 KB Execution killed with signal 9
80 Runtime error 187 ms 65540 KB Execution killed with signal 9
81 Runtime error 317 ms 65540 KB Execution killed with signal 9
82 Runtime error 216 ms 65540 KB Execution killed with signal 9
83 Runtime error 240 ms 65540 KB Execution killed with signal 9
84 Runtime error 201 ms 65540 KB Execution killed with signal 9
85 Runtime error 219 ms 65540 KB Execution killed with signal 9
86 Runtime error 220 ms 65540 KB Execution killed with signal 9
87 Runtime error 218 ms 65540 KB Execution killed with signal 9
88 Runtime error 264 ms 65540 KB Execution killed with signal 9
89 Runtime error 216 ms 65540 KB Execution killed with signal 9
90 Runtime error 254 ms 65540 KB Execution killed with signal 9
91 Runtime error 264 ms 65540 KB Execution killed with signal 9
92 Runtime error 249 ms 65540 KB Execution killed with signal 9