oj.uz

답안 #309217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309217 2020-10-02T22:24:31 Z sofapuden Mecho (IOI09_mecho) C++14
0 / 100
 826 ms 65540 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<int>> 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] < now.f.s)return;
	vis[now.s.f][now.s.s] = now.f.s;
	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] > now.f.s/k+!!(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] > now.f.s/k+!!(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 != 0){
		if(V[now.s.f-1][now.s.s] > now.f.s/k+!!(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 != 0){
		if(V[now.s.f][now.s.s-1] > (now.f.s/k)+!!(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}});
		}
	}

			
}
	
	
	

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<int> (n, 100000));
	
	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] = 100000;}
			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 Incorrect 0 ms 256 KB Output isn't correct
2 Incorrect 0 ms 256 KB Output isn't correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 490 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1 ms 512 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 640 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 625 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 649 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Incorrect 1 ms 384 KB Output isn't correct
16 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 1 ms 384 KB Output isn't correct
18 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Incorrect 1 ms 256 KB Output isn't correct
20 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Incorrect 1 ms 384 KB Output isn't correct
22 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Incorrect 1 ms 384 KB Output isn't correct
24 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Incorrect 1 ms 384 KB Output isn't correct
26 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Incorrect 1 ms 384 KB Output isn't correct
28 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Incorrect 1 ms 384 KB Output isn't correct
30 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Incorrect 1 ms 384 KB Output isn't correct
32 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Incorrect 12 ms 1536 KB Output isn't correct
34 Runtime error 14 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 22 ms 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Incorrect 15 ms 1792 KB Output isn't correct
37 Runtime error 18 ms 3456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 25 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Incorrect 20 ms 2176 KB Output isn't correct
40 Runtime error 24 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 32 ms 4484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Incorrect 25 ms 2816 KB Output isn't correct
43 Runtime error 28 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 40 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Incorrect 34 ms 3328 KB Output isn't correct
46 Runtime error 35 ms 6392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 47 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Incorrect 39 ms 3840 KB Output isn't correct
49 Runtime error 42 ms 7416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 56 ms 7928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Incorrect 47 ms 4352 KB Output isn't correct
52 Runtime error 47 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 65 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Incorrect 53 ms 4856 KB Output isn't correct
55 Runtime error 54 ms 9724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 76 ms 10232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Incorrect 65 ms 5496 KB Output isn't correct
58 Runtime error 63 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 86 ms 11512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Incorrect 70 ms 6136 KB Output isn't correct
61 Runtime error 72 ms 12368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 99 ms 13048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
63 Runtime error 81 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 82 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 83 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 81 ms 12388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 84 ms 12516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Incorrect 95 ms 7032 KB Output isn't correct
69 Runtime error 108 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 99 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 98 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 87 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 481 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 713 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 609 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 613 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 826 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 701 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 708 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 710 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 716 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 701 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 756 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 691 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 723 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 783 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 684 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 491 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 705 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 509 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 508 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 503 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)