답안 #896732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896732	2024-01-02T03:33:25 Z	LCJLY	Mecho (IOI09_mecho)	C++14	22 / 100	250 ms	30392 KB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

void solve(){	
	int n,k;
	cin >> n >> k;
	
	string arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	int l=0;
	int r=n;
	int best=-1;
	int mid;
	
	pii start;
	pii done;
	
	int dist[n+5][n+5];
	memset(dist,-1,sizeof(dist));
	queue<pii>q;
	for(int x=0;x<n;x++){
		for(int y=0;y<n;y++){
			if(arr[x][y]=='H'){
				q.push({x,y});
				dist[x][y]=0;
			}
			else if(arr[x][y]=='M') start={x,y};
			else if(arr[x][y]=='D') done={x,y};
		}
	}
	
	pii dir[4]={
		{0,1},
		{0,-1},
		{1,0},
		{-1,0},
	};
	
	while(!q.empty()){
		pii cur=q.front();
		q.pop();
		for(auto it:dir){
			int newx=cur.first+it.first;
			int newy=cur.second+it.second;
			if(newx<0||newy<0||newx>=n||newy>=n) continue;
			if(dist[newx][newy]!=-1) continue;
			dist[newx][newy]=dist[cur.first][cur.second]+1;
			q.push({newx,newy});
		}
	}
	
	//for(int x=0;x<n;x++){
		//for(int y=0;y<n;y++){
			//cout << dist[x][y] << " ";
		//}
		//cout << "\n";
	//}

	
	while(l<=r){
		mid=(l+r)/2;
		
		int dist2[n][n];
		
		memset(dist2,-1,sizeof(dist2));
		dist2[start.first][start.second]=k*mid;
		q.push({start.first,start.second});
		bool visited[n+5][n+5];
		memset(visited,0,sizeof(visited));
		
		for(int x=0;x<n;x++){
			vector<pii>storage;
			int target=(x+1+mid)*k;
			while(!q.empty()){
				pii cur=q.front();
				q.pop();
				//show3(cur.first,cur.first,cur.second,cur.second,dist2,dist2[cur.first][cur.second]);
				//show(check,(dist2[cur.first][cur.second]+k-1)/k);
				//show(x+mid+1,x+mid+1);
				if((dist2[cur.first][cur.second]+k-1)/k==x+mid+1&&x+mid+1<dist[cur.first][cur.second]){
					//show3(cur.first,cur.first,cur.second,cur.second,x,x);
					storage.push_back({cur.first,cur.second});
					visited[cur.first][cur.second]=1;
				}
				if(dist2[cur.first][cur.second]>=target) continue;
				for(auto it:dir){
					int newx=cur.first+it.first;
					int newy=cur.second+it.second;
					if(newx<0||newy<0||newx>=n||newy>=n) continue;
					if(dist2[newx][newy]!=-1) continue;
					dist2[newx][newy]=dist2[cur.first][cur.second]+1;
					q.push({newx,newy});
				}
			}
			
			for(auto it:storage) q.push(it);
		}

		//for(int x=0;x<n;x++){
			//for(int y=0;y<n;y++){
				//cout << dist2[x][y] << " ";
			//}
			//cout << "\n";
		//}
		
		if(visited[done.first][done.second]){
			best=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout << best;
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("out.txt", "w", stdout);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}





		


		
		
	

Subtask #1

22.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	0 ms	344 KB	Output isn't correct
5	Incorrect	0 ms	348 KB	Output isn't correct
6	Incorrect	0 ms	348 KB	Output isn't correct
7	Incorrect	116 ms	12848 KB	Output isn't correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	500 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Incorrect	1 ms	348 KB	Output isn't correct
13	Incorrect	1 ms	344 KB	Output isn't correct
14	Correct	1 ms	344 KB	Output is correct
15	Incorrect	1 ms	348 KB	Output isn't correct
16	Incorrect	0 ms	348 KB	Output isn't correct
17	Incorrect	0 ms	344 KB	Output isn't correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Incorrect	0 ms	348 KB	Output isn't correct
20	Incorrect	0 ms	348 KB	Output isn't correct
21	Incorrect	1 ms	348 KB	Output isn't correct
22	Incorrect	0 ms	348 KB	Output isn't correct
23	Incorrect	0 ms	348 KB	Output isn't correct
24	Incorrect	1 ms	348 KB	Output isn't correct
25	Incorrect	0 ms	348 KB	Output isn't correct
26	Incorrect	1 ms	348 KB	Output isn't correct
27	Incorrect	1 ms	348 KB	Output isn't correct
28	Incorrect	1 ms	604 KB	Output isn't correct
29	Incorrect	1 ms	348 KB	Output isn't correct
30	Incorrect	1 ms	604 KB	Output isn't correct
31	Incorrect	1 ms	348 KB	Output isn't correct
32	Incorrect	1 ms	856 KB	Output isn't correct
33	Incorrect	8 ms	2652 KB	Output isn't correct
34	Incorrect	21 ms	4312 KB	Output isn't correct
35	Incorrect	38 ms	5212 KB	Output isn't correct
36	Incorrect	10 ms	3160 KB	Output isn't correct
37	Incorrect	28 ms	5252 KB	Output isn't correct
38	Incorrect	51 ms	7520 KB	Output isn't correct
39	Incorrect	15 ms	4384 KB	Output isn't correct
40	Incorrect	36 ms	6492 KB	Output isn't correct
41	Incorrect	68 ms	8264 KB	Output isn't correct
42	Incorrect	19 ms	4696 KB	Output isn't correct
43	Incorrect	45 ms	8612 KB	Output isn't correct
44	Incorrect	78 ms	9952 KB	Output isn't correct
45	Incorrect	27 ms	5720 KB	Output isn't correct
46	Incorrect	54 ms	9880 KB	Output isn't correct
47	Incorrect	119 ms	15124 KB	Output isn't correct
48	Incorrect	27 ms	6744 KB	Output isn't correct
49	Incorrect	66 ms	11764 KB	Output isn't correct
50	Incorrect	118 ms	16908 KB	Output isn't correct
51	Incorrect	29 ms	8024 KB	Output isn't correct
52	Incorrect	86 ms	14964 KB	Output isn't correct
53	Incorrect	162 ms	16800 KB	Output isn't correct
54	Incorrect	28 ms	9048 KB	Output isn't correct
55	Incorrect	98 ms	17660 KB	Output isn't correct
56	Incorrect	173 ms	19156 KB	Output isn't correct
57	Incorrect	38 ms	10332 KB	Output isn't correct
58	Incorrect	114 ms	19312 KB	Output isn't correct
59	Incorrect	244 ms	28312 KB	Output isn't correct
60	Incorrect	42 ms	11868 KB	Output isn't correct
61	Incorrect	131 ms	20100 KB	Output isn't correct
62	Incorrect	250 ms	30392 KB	Output isn't correct
63	Incorrect	24 ms	11868 KB	Output isn't correct
64	Incorrect	216 ms	22220 KB	Output isn't correct
65	Incorrect	54 ms	11928 KB	Output isn't correct
66	Incorrect	20 ms	11868 KB	Output isn't correct
67	Incorrect	31 ms	11868 KB	Output isn't correct
68	Incorrect	21 ms	12124 KB	Output isn't correct
69	Incorrect	28 ms	12184 KB	Output isn't correct
70	Incorrect	24 ms	12124 KB	Output isn't correct
71	Incorrect	23 ms	12120 KB	Output isn't correct
72	Incorrect	35 ms	12624 KB	Output isn't correct
73	Incorrect	44 ms	12380 KB	Output isn't correct
74	Correct	116 ms	15840 KB	Output is correct
75	Correct	69 ms	12380 KB	Output is correct
76	Correct	66 ms	12380 KB	Output is correct
77	Correct	67 ms	12380 KB	Output is correct
78	Correct	87 ms	12124 KB	Output is correct
79	Correct	121 ms	16576 KB	Output is correct
80	Correct	76 ms	12124 KB	Output is correct
81	Correct	78 ms	12124 KB	Output is correct
82	Correct	68 ms	12120 KB	Output is correct
83	Correct	93 ms	12300 KB	Output is correct
84	Correct	159 ms	19624 KB	Output is correct
85	Correct	85 ms	12504 KB	Output is correct
86	Correct	94 ms	12308 KB	Output is correct
87	Correct	102 ms	12592 KB	Output is correct
88	Correct	107 ms	12432 KB	Output is correct
89	Correct	193 ms	20328 KB	Output is correct
90	Correct	107 ms	12840 KB	Output is correct
91	Correct	109 ms	13168 KB	Output is correct
92	Correct	90 ms	12532 KB	Output is correct