oj.uz

답안 #946715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946715 2024-03-15T00:02:34 Z narsuk Mecho (IOI09_mecho) C++17
38 / 100
 1000 ms 11200 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+1)/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
38.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 17 ms 1884 KB Execution killed with signal 11
8 Incorrect 1 ms 348 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 2 ms 500 KB Output is correct
14 Incorrect 22 ms 556 KB Output isn't correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 524 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 5 ms 344 KB Output is correct
26 Correct 4 ms 344 KB Output is correct
27 Correct 11 ms 596 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 14 ms 612 KB Output is correct
30 Correct 5 ms 604 KB Output is correct
31 Correct 10 ms 632 KB Output is correct
32 Correct 6 ms 604 KB Output is correct
33 Execution timed out 1091 ms 2876 KB Time limit exceeded
34 Correct 448 ms 2968 KB Output is correct
35 Execution timed out 1042 ms 4928 KB Time limit exceeded
36 Execution timed out 1082 ms 3768 KB Time limit exceeded
37 Correct 668 ms 3804 KB Output is correct
38 Execution timed out 1035 ms 5696 KB Time limit exceeded
39 Execution timed out 1034 ms 4484 KB Time limit exceeded
40 Correct 961 ms 4288 KB Output is correct
41 Execution timed out 1064 ms 7256 KB Time limit exceeded
42 Execution timed out 1051 ms 5276 KB Time limit exceeded
43 Execution timed out 1063 ms 5152 KB Time limit exceeded
44 Execution timed out 1029 ms 7204 KB Time limit exceeded
45 Execution timed out 1060 ms 6076 KB Time limit exceeded
46 Execution timed out 1027 ms 5968 KB Time limit exceeded
47 Execution timed out 1096 ms 9188 KB Time limit exceeded
48 Execution timed out 1077 ms 7132 KB Time limit exceeded
49 Execution timed out 1050 ms 7232 KB Time limit exceeded
50 Execution timed out 1053 ms 11200 KB Time limit exceeded
51 Incorrect 23 ms 2392 KB Output isn't correct
52 Incorrect 39 ms 2392 KB Output isn't correct
53 Execution timed out 1077 ms 4644 KB Time limit exceeded
54 Incorrect 23 ms 2392 KB Output isn't correct
55 Incorrect 32 ms 2280 KB Output isn't correct
56 Execution timed out 1081 ms 4636 KB Time limit exceeded
57 Incorrect 23 ms 2392 KB Output isn't correct
58 Incorrect 33 ms 2288 KB Output isn't correct
59 Execution timed out 1050 ms 4804 KB Time limit exceeded
60 Runtime error 17 ms 1880 KB Execution killed with signal 11
61 Runtime error 17 ms 1920 KB Execution killed with signal 11
62 Runtime error 17 ms 1884 KB Execution killed with signal 11
63 Runtime error 17 ms 1884 KB Execution killed with signal 11
64 Runtime error 17 ms 1972 KB Execution killed with signal 11
65 Runtime error 17 ms 1768 KB Execution killed with signal 11
66 Runtime error 17 ms 1872 KB Execution killed with signal 11
67 Runtime error 17 ms 1768 KB Execution killed with signal 11
68 Runtime error 18 ms 1900 KB Execution killed with signal 11
69 Runtime error 18 ms 1884 KB Execution killed with signal 11
70 Runtime error 17 ms 1892 KB Execution killed with signal 11
71 Runtime error 20 ms 1884 KB Execution killed with signal 11
72 Runtime error 20 ms 1876 KB Execution killed with signal 11
73 Runtime error 17 ms 1884 KB Execution killed with signal 11
74 Runtime error 17 ms 1884 KB Execution killed with signal 11
75 Runtime error 16 ms 2084 KB Execution killed with signal 11
76 Runtime error 22 ms 1780 KB Execution killed with signal 11
77 Runtime error 17 ms 1884 KB Execution killed with signal 11
78 Runtime error 17 ms 1884 KB Execution killed with signal 11
79 Runtime error 16 ms 1884 KB Execution killed with signal 11
80 Runtime error 16 ms 1884 KB Execution killed with signal 11
81 Runtime error 17 ms 1884 KB Execution killed with signal 11
82 Runtime error 24 ms 1808 KB Execution killed with signal 11
83 Runtime error 17 ms 1884 KB Execution killed with signal 11
84 Runtime error 17 ms 1884 KB Execution killed with signal 11
85 Runtime error 16 ms 1884 KB Execution killed with signal 11
86 Runtime error 17 ms 1884 KB Execution killed with signal 11
87 Runtime error 17 ms 1884 KB Execution killed with signal 11
88 Runtime error 17 ms 1884 KB Execution killed with signal 11
89 Runtime error 16 ms 1880 KB Execution killed with signal 11
90 Runtime error 16 ms 1824 KB Execution killed with signal 11
91 Runtime error 17 ms 1792 KB Execution killed with signal 11
92 Runtime error 17 ms 1752 KB Execution killed with signal 11