oj.uz

Submission #947228

# Submission time Handle Problem Language Result Execution time Memory
947228 2024-03-15T18:04:04 Z narsuk Mecho (IOI09_mecho) C++17
15 / 100
 243 ms 5640 KB 
#include <bits/stdc++.h>
using namespace std;
//
#define ll long long int
 
#define endl "\n"; 
 
const int maxn = 601;

// array<int,n>
// pq 


int n,st;

pair<int,int>mv[4]={ {0,1},{0,-1} , {1,0}, {-1,0} };

char g[maxn][maxn];
char g1[maxn][maxn];
char g2[maxn][maxn];

bool val(int x , int y){
	if(x<0 || x>=n || y<0 || y>=n || g[x][y]=='T' )return 0;
	return 1;
}
 

int xc,yc;
int xcc;
int ycc;
int beetime[maxn][maxn];

void bbfs(){
	int vis[n][n];
	queue<pair<pair<int,int>,int>>q;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			beetime[i][j]=INT_MAX;
			if(g1[i][j]=='H'){
				q.push({{i,j},0}); 
			}
			vis[i][j]=0;
		}
	}
	while(!q.empty()){
		pair<int,int>cur;
		cur=q.front().first;
		int dt = q.front().second;
		q.pop();
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;

		if(g1[cur.first][cur.second]=='D' || g1[cur.first][cur.second]=='T'){
			continue;
		} 
		beetime[cur.first][cur.second]=dt;
		// cout<<cur.first<<" "<<cur.second<<endl;
		for(auto ele : mv){
			int xx = cur.first+ele.first;
			int yy = cur.second+ele.second;
			if(val(xx,yy)){
				q.push({{xx,yy},dt+1});
			}
		}
	}

}




// int mbfs(int x){
bool tme(int marc , int bee){
	int ccur = marc/st;
	if(ccur*st!=marc){
		return (marc/st)-1<bee;
	}
	return marc/st <bee;
}

 

bool check(int x){

	bbfs();


	queue<pair<pair<int,int>,int>>q;
	bool vis[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			vis[i][j]=0;
		}
	}

	q.push({{xc,yc},0});
	while(!q.empty()){
		pair<int,int>cur=q.front().first;
		int dt = q.front().second;
		q.pop();
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;

		for(auto ele :mv){
			int xx = cur.first+ele.first;
			int yy = cur.second+ele.second;

			if(val(xx,yy) && !vis[xx][yy] && tme(dt+1 , beetime[xx][yy]-x) && g[xx][yy]!='H'){
				q.push({{xx,yy} , dt+1});
			}
		}

	}
	// for(int i=0;i<n;i++){
	// 	for(int j=0;j<n;j++){
	// 		cout<<vis[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }

	for(auto ele : mv){
		int xx = xcc+ele.first;
		int yy = ycc+ele.second;

		if(val(xx,yy) && vis[xx][yy]==1){
		// cout<<xx<<" "<<yy<<endl;
			return 1;
		}
	}

	return 0;
}

void solu(){
	cin>>n>>st;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>g[i][j];
			g1[i][j]=g[i][j];
			if(g[i][j]=='M'){
				xc=i;
				yc=j;
			}
			if(g[i][j]=='D'){
				xcc = i;
				ycc = j;
			}
		}
	}
	// cout<<endl;
	int l=0;
	int r = 1e6;
	int ans=0;
	while(l<r){
		int mid = l + (r-l+1)/2;
		// cout<<mid<<endl;
		if(check(mid)){
			ans=max(mid,ans);
			l=mid;
		}else{
			r=mid-1;
		}
	}
	// cout<<check(2)<<endl;
	cout<<ans<<endl;


}
int main(){
		// ios_base::sync_with_stdio(0);
		// cin.tie(0);
		// int cass;
		// cin>>cass; 
		// for(int i=0;i<cass;i++)
		solu();
    return 0;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Runtime error 20 ms 5224 KB Execution killed with signal 11
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2396 KB Output isn't correct
12 Incorrect 2 ms 2648 KB Output isn't correct
13 Incorrect 2 ms 2396 KB Output isn't correct
14 Incorrect 3 ms 2648 KB Output isn't correct
15 Correct 1 ms 2392 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Correct 1 ms 2396 KB Output is correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 Correct 1 ms 2396 KB Output is correct
20 Incorrect 1 ms 2396 KB Output isn't correct
21 Correct 1 ms 2392 KB Output is correct
22 Incorrect 1 ms 2396 KB Output isn't correct
23 Correct 2 ms 2396 KB Output is correct
24 Incorrect 1 ms 2396 KB Output isn't correct
25 Correct 2 ms 2652 KB Output is correct
26 Incorrect 2 ms 2396 KB Output isn't correct
27 Correct 2 ms 2648 KB Output is correct
28 Incorrect 2 ms 2652 KB Output isn't correct
29 Correct 2 ms 2652 KB Output is correct
30 Incorrect 2 ms 2648 KB Output isn't correct
31 Correct 2 ms 2652 KB Output is correct
32 Incorrect 2 ms 2652 KB Output isn't correct
33 Correct 35 ms 3300 KB Output is correct
34 Incorrect 42 ms 3320 KB Output isn't correct
35 Incorrect 81 ms 3164 KB Output isn't correct
36 Correct 47 ms 3436 KB Output is correct
37 Incorrect 42 ms 3616 KB Output isn't correct
38 Incorrect 103 ms 3420 KB Output isn't correct
39 Correct 55 ms 3676 KB Output is correct
40 Incorrect 52 ms 3676 KB Output isn't correct
41 Incorrect 138 ms 3776 KB Output isn't correct
42 Correct 67 ms 3932 KB Output is correct
43 Incorrect 65 ms 3932 KB Output isn't correct
44 Incorrect 165 ms 3932 KB Output isn't correct
45 Correct 81 ms 4188 KB Output is correct
46 Incorrect 77 ms 4188 KB Output isn't correct
47 Incorrect 200 ms 4184 KB Output isn't correct
48 Correct 98 ms 4532 KB Output is correct
49 Incorrect 106 ms 4432 KB Output isn't correct
50 Incorrect 243 ms 4432 KB Output isn't correct
51 Incorrect 20 ms 4440 KB Output isn't correct
52 Incorrect 58 ms 4480 KB Output isn't correct
53 Incorrect 75 ms 4360 KB Output isn't correct
54 Incorrect 25 ms 4440 KB Output isn't correct
55 Incorrect 62 ms 4436 KB Output isn't correct
56 Incorrect 84 ms 4544 KB Output isn't correct
57 Incorrect 23 ms 4436 KB Output isn't correct
58 Incorrect 66 ms 4440 KB Output isn't correct
59 Incorrect 92 ms 4692 KB Output isn't correct
60 Runtime error 20 ms 5456 KB Execution killed with signal 11
61 Runtime error 22 ms 5460 KB Execution killed with signal 11
62 Runtime error 22 ms 5460 KB Execution killed with signal 11
63 Runtime error 20 ms 5572 KB Execution killed with signal 11
64 Runtime error 19 ms 5468 KB Execution killed with signal 11
65 Runtime error 20 ms 5456 KB Execution killed with signal 11
66 Runtime error 22 ms 5456 KB Execution killed with signal 11
67 Runtime error 24 ms 5492 KB Execution killed with signal 11
68 Runtime error 20 ms 5640 KB Execution killed with signal 11
69 Runtime error 20 ms 5580 KB Execution killed with signal 11
70 Runtime error 20 ms 5464 KB Execution killed with signal 11
71 Runtime error 20 ms 5464 KB Execution killed with signal 11
72 Runtime error 22 ms 5456 KB Execution killed with signal 11
73 Runtime error 19 ms 5392 KB Execution killed with signal 11
74 Runtime error 20 ms 5456 KB Execution killed with signal 11
75 Runtime error 20 ms 5460 KB Execution killed with signal 11
76 Runtime error 20 ms 5376 KB Execution killed with signal 11
77 Runtime error 19 ms 5564 KB Execution killed with signal 11
78 Runtime error 20 ms 5496 KB Execution killed with signal 11
79 Runtime error 20 ms 5468 KB Execution killed with signal 11
80 Runtime error 22 ms 5256 KB Execution killed with signal 11
81 Runtime error 20 ms 5468 KB Execution killed with signal 11
82 Runtime error 20 ms 5316 KB Execution killed with signal 11
83 Runtime error 19 ms 5464 KB Execution killed with signal 11
84 Runtime error 19 ms 5204 KB Execution killed with signal 11
85 Runtime error 20 ms 5464 KB Execution killed with signal 11
86 Runtime error 20 ms 5500 KB Execution killed with signal 11
87 Runtime error 20 ms 5468 KB Execution killed with signal 11
88 Runtime error 20 ms 5468 KB Execution killed with signal 11
89 Runtime error 19 ms 5428 KB Execution killed with signal 11
90 Runtime error 20 ms 5484 KB Execution killed with signal 11
91 Runtime error 20 ms 5468 KB Execution killed with signal 11
92 Runtime error 20 ms 5520 KB Execution killed with signal 11