oj.uz

답안 #309208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309208 2020-10-02T21:54:59 Z sofapuden Mecho (IOI09_mecho) C++14
0 / 100
 683 ms 65544 KB 
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

int n, k;
bool ok = 0;

pair<int,int> sta, en;

vector<string> G;
vector<vector<int>> V;
vector<vector<bool>> vis;

queue<pair<pair<int,int>,int>> Q;

auto cmp = [](pair<pair<int,int>,pair<int,int>> l, pair<pair<int,int>,pair<int,int>> r){
	if(l.f.f != r.f.f)return l.f.f < r.f.f;
	return l.f.s > r.f.s;
};
priority_queue<pair<pair<int,int>,pair<int,int>>, vector<pair<pair<int,int>,pair<int,int>>>, decltype(cmp)> PQ(cmp);

void fin(pair<pair<int,int>,pair<int,int>> now){
	if(vis[now.s.f][now.s.s])return;
	if(now.s == en){cout << now.f.f << "\n";ok = 1;return;}
	if(now.s.f != n){
		if(V[now.s.f+1][now.s.s]-1 > now.f.s/k){
			PQ.push({{min(V[now.s.f+1][now.s.s]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f+1,now.s.s}});
		}
	}
	
	if(now.s.s != n){
		if(V[now.s.f][now.s.s+1]-1 > now.f.s/k){
			PQ.push({{min(V[now.s.f][now.s.s+1]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f,now.s.s+1}});
		}
	}
	
	if(now.s.f != n){
		if(V[now.s.f-1][now.s.s]-1 > now.f.s/k){
			PQ.push({{min(V[now.s.f-1][now.s.s]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f-1,now.s.s}});
		}
	}
	
	if(now.s.s != n){
		if(V[now.s.f][now.s.s-1]-1 > now.f.s/k){
			PQ.push({{min(V[now.s.f][now.s.s-1]-now.f.s/k,now.f.f), now.f.s+1},{now.s.f,now.s.s-1}});
		}
	}

			
}
	
	
	

void search(pair<pair<int,int>,int> now){
	if(now.f.f < 0 || now.f.s < 0 || now.f.f >= n || now.f.s >= n)return;
	if(V[now.f.f][now.f.s] != -1)return;
	V[now.f.f][now.f.s] = now.s;
	Q.push({{now.f.f-1,now.f.s},now.s+1});
	Q.push({{now.f.f+1,now.f.s},now.s+1});
	Q.push({{now.f.f,now.f.s-1},now.s+1});
	Q.push({{now.f.f,now.f.s+1},now.s+1});
}

int main(){ 
	cin >> n >> k;
	G.resize(n);
	V.resize(n, vector<int> (n,-1));
	vis.resize(n, vector<bool> (n, false));
	
	for(auto &x : G)cin >> x;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(G[i][j] == 'T')V[i][j] = -2;
			if(G[i][j] == 'M')sta = {i,j};
			if(G[i][j] == 'D'){en = {i,j};V[i][j] = INT_MAX;}
			if(G[i][j] == 'H')Q.push({{i,j},0});
		}
	}
	while(!Q.empty()){
		auto x = Q.front();
		Q.pop();
		search(x);
	}
	//for(int i = 0; i < n; ++i){
		//for(int j = 0; j < n; ++j){
			//cout << V[i][j] << " ";
		//}
		//cout << "\n";
	//}
	PQ.push({{V[sta.f][sta.s], 0},sta});
	while(!PQ.empty()){
		auto x = PQ.top();
		PQ.pop();
		//cout << x.f.f << " " << x.f.s << " " << x.s.f << " " << x.s.s << "\n";
		fin(x);
		if(ok)break;
	}
	if(!ok)cout << -1 << "\n";
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 0 ms 256 KB Output isn't correct
6 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 95 ms 8392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 1 ms 384 KB Output isn't correct
13 Runtime error 213 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 233 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 1 ms 420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 13 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 14 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 340 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 16 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 17 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 348 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 21 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 21 ms 2688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 354 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 27 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 27 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 357 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Runtime error 31 ms 4220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 32 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 368 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 36 ms 4728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 38 ms 4728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 375 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 44 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 45 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 376 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 49 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 52 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 387 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Runtime error 58 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 58 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 396 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Runtime error 66 ms 7420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 66 ms 7544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 407 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 79 ms 7544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 78 ms 7416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 78 ms 7416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 80 ms 7416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 80 ms 7416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 674 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 680 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 602 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 683 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 421 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 300 ms 65544 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 101 ms 10548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 103 ms 10548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 103 ms 10552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 101 ms 10548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 432 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 398 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 439 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 470 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 420 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 318 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 351 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 394 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 329 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 330 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 396 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 474 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 457 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 465 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 471 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)