oj.uz

Submission #309206

# Submission time Handle Problem Language Result Execution time Memory
309206 2020-10-02T21:52:32 Z sofapuden Mecho (IOI09_mecho) C++14
0 / 100
 672 ms 65540 KB 
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

int n, k;

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";exit(0);}
	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);
	}
	cout << -1 << "\n";
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory 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 109 ms 9040 KB Execution killed with signal 11 (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 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 228 ms 65536 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 640 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 512 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 512 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 2 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 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 338 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 17 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 17 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 350 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 21 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 22 ms 2808 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 26 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 27 ms 3828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 360 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Runtime error 32 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 32 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 360 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 39 ms 4984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 39 ms 4984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 368 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 43 ms 5752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 44 ms 5752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 378 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 50 ms 6392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 51 ms 6392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 384 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Runtime error 57 ms 7292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 62 ms 7160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 392 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Runtime error 65 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 66 ms 8056 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 80 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 78 ms 8168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 79 ms 8184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 78 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 81 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 671 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 671 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 603 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 672 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 409 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 293 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 99 ms 11188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 98 ms 11184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 99 ms 11316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 104 ms 11188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 411 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 403 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 406 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 476 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 395 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 318 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 327 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 398 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 324 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 327 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 384 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 476 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 460 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 459 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 473 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)