답안 #896733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896733	2024-01-02T03:36:37 Z	LCJLY	Mecho (IOI09_mecho)	C++14	22 / 100	238 ms	21504 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});
		}
	}
	
	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();
				if((dist2[cur.first][cur.second]+k-1)/k==x+mid+1&&x+mid+1<dist[cur.first][cur.second]){
					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;
					if(arr[newx][newy]=='T') continue;
					dist2[newx][newy]=dist2[cur.first][cur.second]+1;
					q.push({newx,newy});
				}
			}
			
			for(auto it:storage) q.push(it);
		}
		
		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	348 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	348 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	113 ms	12856 KB	Output isn't correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 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	348 KB	Output isn't correct
14	Correct	1 ms	348 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	344 KB	Output isn't correct
19	Incorrect	1 ms	600 KB	Output isn't correct
20	Incorrect	1 ms	348 KB	Output isn't correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Incorrect	0 ms	348 KB	Output isn't correct
23	Incorrect	1 ms	348 KB	Output isn't correct
24	Incorrect	0 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	0 ms	348 KB	Output isn't correct
29	Incorrect	1 ms	344 KB	Output isn't correct
30	Incorrect	0 ms	348 KB	Output isn't correct
31	Incorrect	0 ms	348 KB	Output isn't correct
32	Incorrect	1 ms	348 KB	Output isn't correct
33	Incorrect	3 ms	2652 KB	Output isn't correct
34	Incorrect	6 ms	2704 KB	Output isn't correct
35	Incorrect	29 ms	4148 KB	Output isn't correct
36	Incorrect	4 ms	3164 KB	Output isn't correct
37	Incorrect	7 ms	3176 KB	Output isn't correct
38	Incorrect	35 ms	5400 KB	Output isn't correct
39	Incorrect	5 ms	3928 KB	Output isn't correct
40	Incorrect	9 ms	3932 KB	Output isn't correct
41	Incorrect	48 ms	6284 KB	Output isn't correct
42	Incorrect	10 ms	4732 KB	Output isn't correct
43	Incorrect	13 ms	4976 KB	Output isn't correct
44	Incorrect	59 ms	7784 KB	Output isn't correct
45	Incorrect	8 ms	5724 KB	Output isn't correct
46	Incorrect	13 ms	5764 KB	Output isn't correct
47	Incorrect	73 ms	9828 KB	Output isn't correct
48	Incorrect	9 ms	6744 KB	Output isn't correct
49	Incorrect	16 ms	6748 KB	Output isn't correct
50	Incorrect	107 ms	10888 KB	Output isn't correct
51	Incorrect	11 ms	7768 KB	Output isn't correct
52	Incorrect	18 ms	7908 KB	Output isn't correct
53	Incorrect	127 ms	12404 KB	Output isn't correct
54	Incorrect	13 ms	9048 KB	Output isn't correct
55	Incorrect	21 ms	9052 KB	Output isn't correct
56	Incorrect	137 ms	14216 KB	Output isn't correct
57	Incorrect	15 ms	10332 KB	Output isn't correct
58	Incorrect	30 ms	10412 KB	Output isn't correct
59	Incorrect	206 ms	19956 KB	Output isn't correct
60	Incorrect	17 ms	11864 KB	Output isn't correct
61	Incorrect	28 ms	11868 KB	Output isn't correct
62	Incorrect	238 ms	21504 KB	Output isn't correct
63	Incorrect	22 ms	11856 KB	Output isn't correct
64	Incorrect	214 ms	18832 KB	Output isn't correct
65	Incorrect	136 ms	11864 KB	Output isn't correct
66	Incorrect	18 ms	11864 KB	Output isn't correct
67	Correct	63 ms	11880 KB	Output is correct
68	Incorrect	22 ms	12124 KB	Output isn't correct
69	Incorrect	30 ms	12356 KB	Output isn't correct
70	Incorrect	20 ms	12008 KB	Output isn't correct
71	Incorrect	20 ms	12124 KB	Output isn't correct
72	Incorrect	24 ms	12124 KB	Output isn't correct
73	Incorrect	46 ms	12376 KB	Output isn't correct
74	Correct	114 ms	15860 KB	Output is correct
75	Correct	71 ms	12572 KB	Output is correct
76	Correct	68 ms	12380 KB	Output is correct
77	Correct	68 ms	12380 KB	Output is correct
78	Correct	81 ms	12332 KB	Output is correct
79	Correct	122 ms	16704 KB	Output is correct
80	Correct	61 ms	12124 KB	Output is correct
81	Correct	81 ms	12340 KB	Output is correct
82	Correct	71 ms	12344 KB	Output is correct
83	Correct	92 ms	12276 KB	Output is correct
84	Correct	189 ms	20304 KB	Output is correct
85	Correct	86 ms	12400 KB	Output is correct
86	Correct	93 ms	12292 KB	Output is correct
87	Correct	93 ms	12488 KB	Output is correct
88	Correct	99 ms	12416 KB	Output is correct
89	Correct	221 ms	21184 KB	Output is correct
90	Correct	150 ms	12868 KB	Output is correct
91	Correct	114 ms	13252 KB	Output is correct
92	Correct	104 ms	12420 KB	Output is correct