oj.uz

답안 #476426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476426 2021-09-26T17:55:47 Z Morley Mecho (IOI09_mecho) C++14
18 / 100
 383 ms 65544 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=0,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
18.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Runtime error 192 ms 65540 KB Execution killed with signal 9
8 Incorrect 1 ms 204 KB Output isn't correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Correct 1 ms 332 KB Output is correct
14 Runtime error 228 ms 65540 KB Execution killed with signal 9
15 Incorrect 0 ms 204 KB Output isn't correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Incorrect 0 ms 204 KB Output isn't correct
18 Incorrect 0 ms 316 KB Output isn't correct
19 Incorrect 0 ms 204 KB Output isn't correct
20 Incorrect 0 ms 332 KB Output isn't correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Incorrect 1 ms 204 KB Output isn't correct
23 Incorrect 1 ms 332 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 1100 KB Output isn't correct
34 Incorrect 5 ms 1100 KB Output isn't correct
35 Runtime error 184 ms 65540 KB Execution killed with signal 9
36 Incorrect 5 ms 1332 KB Output isn't correct
37 Incorrect 5 ms 1228 KB Output isn't correct
38 Runtime error 204 ms 65540 KB Execution killed with signal 9
39 Incorrect 5 ms 1484 KB Output isn't correct
40 Incorrect 6 ms 1484 KB Output isn't correct
41 Runtime error 222 ms 65540 KB Execution killed with signal 9
42 Incorrect 7 ms 1868 KB Output isn't correct
43 Incorrect 8 ms 1868 KB Output isn't correct
44 Runtime error 203 ms 65540 KB Execution killed with signal 9
45 Incorrect 8 ms 2124 KB Output isn't correct
46 Incorrect 9 ms 2124 KB Output isn't correct
47 Runtime error 187 ms 65540 KB Execution killed with signal 9
48 Incorrect 10 ms 2548 KB Output isn't correct
49 Incorrect 10 ms 2508 KB Output isn't correct
50 Runtime error 197 ms 65540 KB Execution killed with signal 9
51 Incorrect 11 ms 2888 KB Output isn't correct
52 Incorrect 11 ms 2872 KB Output isn't correct
53 Runtime error 238 ms 65540 KB Execution killed with signal 9
54 Incorrect 15 ms 3376 KB Output isn't correct
55 Incorrect 14 ms 3268 KB Output isn't correct
56 Runtime error 206 ms 65540 KB Execution killed with signal 9
57 Incorrect 15 ms 3708 KB Output isn't correct
58 Incorrect 16 ms 3840 KB Output isn't correct
59 Runtime error 201 ms 65540 KB Execution killed with signal 9
60 Incorrect 17 ms 4180 KB Output isn't correct
61 Incorrect 17 ms 4172 KB Output isn't correct
62 Runtime error 216 ms 65540 KB Execution killed with signal 9
63 Correct 91 ms 4184 KB Output is correct
64 Correct 156 ms 4304 KB Output is correct
65 Correct 160 ms 4288 KB Output is correct
66 Correct 127 ms 4188 KB Output is correct
67 Incorrect 115 ms 4276 KB Output isn't correct
68 Correct 58 ms 4212 KB Output is correct
69 Correct 40 ms 4280 KB Output is correct
70 Correct 46 ms 4220 KB Output is correct
71 Correct 37 ms 4212 KB Output is correct
72 Correct 33 ms 4224 KB Output is correct
73 Runtime error 197 ms 65536 KB Execution killed with signal 9
74 Runtime error 207 ms 65540 KB Execution killed with signal 9
75 Runtime error 229 ms 65540 KB Execution killed with signal 9
76 Runtime error 231 ms 65540 KB Execution killed with signal 9
77 Runtime error 255 ms 65544 KB Execution killed with signal 9
78 Runtime error 297 ms 65540 KB Execution killed with signal 9
79 Runtime error 187 ms 65536 KB Execution killed with signal 9
80 Runtime error 192 ms 65540 KB Execution killed with signal 9
81 Runtime error 247 ms 65540 KB Execution killed with signal 9
82 Runtime error 383 ms 65540 KB Execution killed with signal 9
83 Runtime error 198 ms 65540 KB Execution killed with signal 9
84 Runtime error 208 ms 65540 KB Execution killed with signal 9
85 Runtime error 201 ms 65540 KB Execution killed with signal 9
86 Runtime error 252 ms 65540 KB Execution killed with signal 9
87 Runtime error 199 ms 65540 KB Execution killed with signal 9
88 Runtime error 249 ms 65540 KB Execution killed with signal 9
89 Runtime error 192 ms 65540 KB Execution killed with signal 9
90 Runtime error 243 ms 65540 KB Execution killed with signal 9
91 Runtime error 254 ms 65540 KB Execution killed with signal 9
92 Runtime error 229 ms 65540 KB Execution killed with signal 9