oj.uz

Submission #309210

# Submission time Handle Problem Language Result Execution time Memory
309210 2020-10-02T21:58:04 Z sofapuden Mecho (IOI09_mecho) C++14
0 / 100
 683 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<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(!vis[now.s.f+1][now.s.s]){
			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(!vis[now.s.f][now.s.s+1]){
			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 != 0){
		if(!vis[now.s.f-1][now.s.s]){
			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 != 0){
		if(!vis[now.s.f][now.s.s-1]){
			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

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Incorrect 1 ms 256 KB Output isn't correct
6 Runtime error 1 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 385 ms 65540 KB Execution killed with signal 9 (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 216 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 236 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 0 ms 384 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 1 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 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Incorrect 13 ms 1024 KB Output isn't correct
34 Runtime error 13 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 349 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Incorrect 15 ms 1152 KB Output isn't correct
37 Runtime error 17 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 354 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 19 ms 1408 KB Output isn't correct
40 Runtime error 22 ms 2688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 358 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Incorrect 24 ms 1920 KB Output isn't correct
43 Runtime error 27 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 359 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Incorrect 28 ms 2176 KB Output isn't correct
46 Runtime error 33 ms 4096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 372 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 34 ms 2432 KB Output isn't correct
49 Runtime error 38 ms 4684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 378 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Incorrect 41 ms 2816 KB Output isn't correct
52 Runtime error 44 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 386 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Incorrect 45 ms 3072 KB Output isn't correct
55 Runtime error 51 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 394 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Incorrect 53 ms 3320 KB Output isn't correct
58 Runtime error 59 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 399 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Incorrect 60 ms 3704 KB Output isn't correct
61 Runtime error 66 ms 7516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 412 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 82 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 78 ms 7420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 78 ms 7544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 681 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 683 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 619 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 680 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 426 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 297 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 399 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 338 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 340 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 452 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 412 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 403 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 412 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 479 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 401 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 327 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 334 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 328 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 337 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 391 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 463 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 467 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 460 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 472 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)