oj.uz

Submission #946714

# Submission time Handle Problem Language Result Execution time Memory
946714 2024-03-14T23:55:20 Z narsuk Mecho (IOI09_mecho) C++14
0 / 100
 1000 ms 11084 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;

void bbfs(int x){
	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++){
			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(dt>x){
			continue;
		}
		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;
		} 
		g1[cur.first][cur.second]='H';
		// 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){

	int vis[n][n];
	queue<pair<pair<int,int>,int>>q;
	int cou = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			// cout<<g1[i][j];
			if(g1[i][j]=='M'){
				q.push({{i,j},0});
				cou++;
			}
			vis[i][j]=0;
		}
		// cout<<endl;
	}
	// cout<<endl;
	if(cou==0){
		return 0;
	}
	while(!q.empty()){
		pair<int,int>cur;
		cur=q.front().first;
		int dt = q.front().second;
		q.pop();
		if(dt>x){
			continue;
		}
		if(g1[cur.first][cur.second]=='D'){
			return 1;
		}
		if(g1[cur.first][cur.second]!='G' && g1[cur.first][cur.second]!='M'){
			continue;
		}
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;
		g1[cur.first][cur.second]='M';
		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});
			}
		}
	}
	return 2;

}
 

bool check(int x){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			g1[i][j]=g[i][j];
		}
	}
	bbfs(x);
	// cout<<"de"<<endl;
	while(1){
		// for(int i=0;i<n;i++){
		// 	for(int j=0;j<n;j++){
		// 		cout<<g1[i][j];
		// 	}
		// 	cout<<endl;
		// }
		// cout<<endl;
		// int cans1 = mbfs(st);
		// cout<<cans1<<endl; 
		// if(cans1==1) return 1; 
		// for(int i=0;i<n;i++){
		// 	for(int j=0;j<n;j++){
		// 		g1[i][j]=g2[i][j];
		// 	}
		// }


		int cans = mbfs(st);
		// cout<<cans<<endl;
		if(cans==0)return 0;
		if(cans==1) return 1; 
		bbfs(1);
	}
}

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;
			}
		}
	}
	// cout<<endl;
	int l=0;
	int r = 1e6;
	int ans=0;
	while(l<r){
		int mid = l + (r-l)/2;
		// cout<<mid<<endl;
		if(check(mid)){
			ans=max(mid,ans);
			l=mid;
		}else{
			r=mid+1;
		}
	}
	// cout<<check(1)<<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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 348 KB Time limit exceeded
2 Execution timed out 1036 ms 348 KB Time limit exceeded
3 Execution timed out 1046 ms 344 KB Time limit exceeded
4 Execution timed out 1056 ms 348 KB Time limit exceeded
5 Execution timed out 1078 ms 348 KB Time limit exceeded
6 Execution timed out 1061 ms 348 KB Time limit exceeded
7 Runtime error 17 ms 1884 KB Execution killed with signal 11
8 Execution timed out 1081 ms 348 KB Time limit exceeded
9 Execution timed out 1053 ms 344 KB Time limit exceeded
10 Execution timed out 1070 ms 348 KB Time limit exceeded
11 Execution timed out 1066 ms 348 KB Time limit exceeded
12 Execution timed out 1028 ms 344 KB Time limit exceeded
13 Execution timed out 1064 ms 348 KB Time limit exceeded
14 Execution timed out 1055 ms 824 KB Time limit exceeded
15 Execution timed out 1064 ms 348 KB Time limit exceeded
16 Execution timed out 1028 ms 344 KB Time limit exceeded
17 Execution timed out 1029 ms 344 KB Time limit exceeded
18 Execution timed out 1026 ms 344 KB Time limit exceeded
19 Execution timed out 1048 ms 348 KB Time limit exceeded
20 Execution timed out 1039 ms 344 KB Time limit exceeded
21 Execution timed out 1040 ms 348 KB Time limit exceeded
22 Execution timed out 1026 ms 344 KB Time limit exceeded
23 Execution timed out 1038 ms 344 KB Time limit exceeded
24 Execution timed out 1055 ms 348 KB Time limit exceeded
25 Execution timed out 1065 ms 348 KB Time limit exceeded
26 Execution timed out 1006 ms 600 KB Time limit exceeded
27 Execution timed out 1035 ms 344 KB Time limit exceeded
28 Execution timed out 1095 ms 344 KB Time limit exceeded
29 Execution timed out 1069 ms 604 KB Time limit exceeded
30 Execution timed out 1026 ms 600 KB Time limit exceeded
31 Execution timed out 1020 ms 600 KB Time limit exceeded
32 Execution timed out 1039 ms 600 KB Time limit exceeded
33 Execution timed out 1049 ms 3056 KB Time limit exceeded
34 Execution timed out 1037 ms 3192 KB Time limit exceeded
35 Execution timed out 1060 ms 4932 KB Time limit exceeded
36 Execution timed out 1062 ms 3816 KB Time limit exceeded
37 Execution timed out 1069 ms 3696 KB Time limit exceeded
38 Execution timed out 1063 ms 5676 KB Time limit exceeded
39 Execution timed out 1046 ms 4600 KB Time limit exceeded
40 Execution timed out 1063 ms 4532 KB Time limit exceeded
41 Execution timed out 1050 ms 7352 KB Time limit exceeded
42 Execution timed out 1058 ms 5160 KB Time limit exceeded
43 Execution timed out 1016 ms 5280 KB Time limit exceeded
44 Execution timed out 1042 ms 7256 KB Time limit exceeded
45 Execution timed out 1050 ms 6176 KB Time limit exceeded
46 Execution timed out 1061 ms 6468 KB Time limit exceeded
47 Execution timed out 1056 ms 9156 KB Time limit exceeded
48 Execution timed out 1029 ms 7064 KB Time limit exceeded
49 Execution timed out 1069 ms 7064 KB Time limit exceeded
50 Execution timed out 1014 ms 11084 KB Time limit exceeded
51 Execution timed out 1037 ms 2392 KB Time limit exceeded
52 Execution timed out 1065 ms 2244 KB Time limit exceeded
53 Execution timed out 1010 ms 4756 KB Time limit exceeded
54 Execution timed out 1032 ms 2392 KB Time limit exceeded
55 Execution timed out 1065 ms 2396 KB Time limit exceeded
56 Execution timed out 1057 ms 4508 KB Time limit exceeded
57 Execution timed out 1031 ms 2392 KB Time limit exceeded
58 Execution timed out 1051 ms 2392 KB Time limit exceeded
59 Execution timed out 1056 ms 4868 KB Time limit exceeded
60 Runtime error 17 ms 1740 KB Execution killed with signal 11
61 Runtime error 17 ms 1884 KB Execution killed with signal 11
62 Runtime error 17 ms 1884 KB Execution killed with signal 11
63 Runtime error 17 ms 1888 KB Execution killed with signal 11
64 Runtime error 16 ms 1884 KB Execution killed with signal 11
65 Runtime error 16 ms 1792 KB Execution killed with signal 11
66 Runtime error 17 ms 1880 KB Execution killed with signal 11
67 Runtime error 17 ms 1884 KB Execution killed with signal 11
68 Runtime error 17 ms 1892 KB Execution killed with signal 11
69 Runtime error 17 ms 1884 KB Execution killed with signal 11
70 Runtime error 16 ms 1884 KB Execution killed with signal 11
71 Runtime error 17 ms 1916 KB Execution killed with signal 11
72 Runtime error 19 ms 1884 KB Execution killed with signal 11
73 Runtime error 17 ms 1880 KB Execution killed with signal 11
74 Runtime error 16 ms 1816 KB Execution killed with signal 11
75 Runtime error 17 ms 1884 KB Execution killed with signal 11
76 Runtime error 17 ms 1916 KB Execution killed with signal 11
77 Runtime error 17 ms 1884 KB Execution killed with signal 11
78 Runtime error 18 ms 1896 KB Execution killed with signal 11
79 Runtime error 17 ms 1884 KB Execution killed with signal 11
80 Runtime error 17 ms 1780 KB Execution killed with signal 11
81 Runtime error 17 ms 1880 KB Execution killed with signal 11
82 Runtime error 17 ms 1884 KB Execution killed with signal 11
83 Runtime error 17 ms 1960 KB Execution killed with signal 11
84 Runtime error 17 ms 1888 KB Execution killed with signal 11
85 Runtime error 17 ms 1828 KB Execution killed with signal 11
86 Runtime error 18 ms 1836 KB Execution killed with signal 11
87 Runtime error 21 ms 1884 KB Execution killed with signal 11
88 Runtime error 17 ms 1896 KB Execution killed with signal 11
89 Runtime error 17 ms 1880 KB Execution killed with signal 11
90 Runtime error 17 ms 1832 KB Execution killed with signal 11
91 Runtime error 17 ms 1788 KB Execution killed with signal 11
92 Runtime error 17 ms 1884 KB Execution killed with signal 11