oj.uz

Submission #947334

# Submission time Handle Problem Language Result Execution time Memory
947334 2024-03-15T22:22:42 Z narsuk Mecho (IOI09_mecho) C++17
84 / 100
 737 ms 10256 KB 
#include <bits/stdc++.h>
using namespace std;
//
#define ll long long int
 
#define endl "\n"; 
 
const int maxn = 801;

// 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];
	int dist[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			vis[i][j]=0;
			dist[i][j]=INT_MAX;
		}
	}

	q.push({{xc,yc},0});
	if(beetime[xc][yc]<=x)q.pop();
	while(!q.empty()){
		pair<int,int>cur=q.front().first;
		int dt = q.front().second;
		dist[cur.first][cur.second]=dt;
		q.pop();
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;
		if(g[cur.first][cur.second]=='D'){
			return 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 && tme(dist[xx][yy] ,beetime[xx][yy]-x)){
		// 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 = n*n;
	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;
}

Compilation message

mecho.cpp: In function 'bool tme(int, int)':
mecho.cpp:74:6: warning: unused variable 'ccur' [-Wunused-variable]
   74 |  int ccur = marc/st;
      |      ^~~~

Subtask #1
84.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 583 ms 8676 KB Output is correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 4732 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Incorrect 3 ms 4700 KB Output isn't correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2492 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Correct 1 ms 2424 KB Output is correct
25 Correct 1 ms 4700 KB Output is correct
26 Correct 1 ms 4700 KB Output is correct
27 Correct 1 ms 4700 KB Output is correct
28 Correct 2 ms 4700 KB Output is correct
29 Correct 2 ms 4700 KB Output is correct
30 Correct 2 ms 4700 KB Output is correct
31 Correct 2 ms 4700 KB Output is correct
32 Correct 2 ms 4700 KB Output is correct
33 Correct 31 ms 5724 KB Output is correct
34 Correct 29 ms 5212 KB Output is correct
35 Correct 75 ms 5396 KB Output is correct
36 Correct 39 ms 5468 KB Output is correct
37 Correct 40 ms 5468 KB Output is correct
38 Correct 94 ms 5584 KB Output is correct
39 Correct 53 ms 5940 KB Output is correct
40 Correct 48 ms 5724 KB Output is correct
41 Correct 128 ms 5864 KB Output is correct
42 Correct 62 ms 5980 KB Output is correct
43 Correct 62 ms 5980 KB Output is correct
44 Correct 164 ms 6236 KB Output is correct
45 Correct 78 ms 6232 KB Output is correct
46 Correct 76 ms 6368 KB Output is correct
47 Correct 180 ms 6224 KB Output is correct
48 Correct 91 ms 6696 KB Output is correct
49 Correct 86 ms 6492 KB Output is correct
50 Correct 225 ms 6492 KB Output is correct
51 Correct 119 ms 7120 KB Output is correct
52 Correct 105 ms 7000 KB Output is correct
53 Correct 284 ms 6992 KB Output is correct
54 Correct 133 ms 7504 KB Output is correct
55 Correct 126 ms 7468 KB Output is correct
56 Correct 321 ms 7248 KB Output is correct
57 Correct 145 ms 7844 KB Output is correct
58 Correct 141 ms 8112 KB Output is correct
59 Correct 397 ms 7916 KB Output is correct
60 Correct 163 ms 8188 KB Output is correct
61 Correct 168 ms 8284 KB Output is correct
62 Correct 429 ms 8276 KB Output is correct
63 Correct 417 ms 8344 KB Output is correct
64 Correct 510 ms 8320 KB Output is correct
65 Correct 451 ms 8380 KB Output is correct
66 Correct 440 ms 8272 KB Output is correct
67 Incorrect 433 ms 8356 KB Output isn't correct
68 Correct 430 ms 8292 KB Output is correct
69 Correct 425 ms 8272 KB Output is correct
70 Correct 427 ms 8272 KB Output is correct
71 Correct 443 ms 8608 KB Output is correct
72 Correct 403 ms 8276 KB Output is correct
73 Correct 577 ms 9992 KB Output is correct
74 Correct 623 ms 10256 KB Output is correct
75 Correct 657 ms 10244 KB Output is correct
76 Correct 737 ms 10248 KB Output is correct
77 Correct 662 ms 10060 KB Output is correct
78 Incorrect 647 ms 9808 KB Output isn't correct
79 Correct 598 ms 10088 KB Output is correct
80 Correct 614 ms 9940 KB Output is correct
81 Correct 628 ms 9864 KB Output is correct
82 Correct 601 ms 9832 KB Output is correct
83 Correct 644 ms 9800 KB Output is correct
84 Correct 631 ms 9572 KB Output is correct
85 Correct 629 ms 9584 KB Output is correct
86 Correct 611 ms 9604 KB Output is correct
87 Correct 578 ms 9936 KB Output is correct
88 Correct 585 ms 9520 KB Output is correct
89 Correct 626 ms 9196 KB Output is correct
90 Correct 611 ms 9336 KB Output is correct
91 Correct 586 ms 9508 KB Output is correct
92 Correct 577 ms 9768 KB Output is correct