답안 #65087 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65087	2018-08-06T15:00:21 Z	TuGSGeReL	Mecho (IOI09_mecho)	C++14	11 / 100	1000 ms	36660 KB

mecho

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
int n,s,l,r,x,y,zu[801][801],bo[801][801],ax,ay;
char c[801][801];
void dfs(int i, int j){
	queue<pair<pair<int,int>,int> >q;
	memset(bo,0,sizeof bo);
	q.push(mp(mp(i,j),0));
	bo[i][j]=1;
	zu[i][j]=0;
	while(!q.empty()){
		int ii=q.front().ff.ff,jj=q.front().ff.ss,zz=q.front().ss;
		if(ii>1 && c[ii-1][jj]!='T' && c[ii-1][jj]!='D' && !bo[ii-1][jj]){
			bo[ii-1][jj]=1;
			zu[ii-1][jj]=min(zu[ii-1][jj],zz+1);
			q.push(mp(mp(ii-1,jj),zz+1));
		}
		if(ii<n && c[ii+1][jj]!='T' && c[ii+1][jj]!='D' && !bo[ii+1][jj]){
			bo[ii+1][jj]=1;
			zu[ii+1][jj]=min(zu[ii+1][jj],zz+1);
			q.push(mp(mp(ii+1,jj),zz+1));
		}
		if(jj>1 && c[ii][jj-1]!='T' && c[ii][jj-1]!='D' && !bo[ii][jj-1]){
			bo[ii][jj-1]=1;
			zu[ii][jj-1]=min(zu[ii][jj-1],zz+1);
			q.push(mp(mp(ii,jj-1),zz+1));
		}
		if(jj<n && c[ii][jj+1]!='T' && c[ii][jj+1]!='D' && !bo[ii][jj+1]){
			bo[ii][jj+1]=1;
			zu[ii][jj+1]=min(zu[ii][jj+1],zz+1);
			q.push(mp(mp(ii,jj+1),zz+1));
		}
		q.pop();
	}
}
bool can(int k){
	queue<pair<pair<int,int>,pair<int,int> > >q;
	memset(bo,0,sizeof bo);
	q.push(mp(mp(x,y),mp(k,0)));
	bo[x][y]=1;
	while(!q.empty()){
		int xx=q.front().ff.ff,yy=q.front().ff.ss,kk=q.front().ss.ff,zz=q.front().ss.ss;
		if(zz==s) zz=0,kk++;
		else zz++;
		if(xx>1 && c[xx-1][yy]!='T' && !bo[xx-1][yy] && zu[xx-1][yy]>kk){
			bo[xx-1][yy]=1;
			q.push(mp(mp(xx-1,yy),mp(kk,zz)));
		}
		if(xx<n && c[xx+1][yy]!='T' && !bo[xx+1][yy] && zu[xx+1][yy]>kk){
			bo[xx+1][yy]=1;
			q.push(mp(mp(xx+1,yy),mp(kk,zz)));
		}
		if(yy>1 && c[xx][yy-1]!='T' && !bo[xx][yy-1] && zu[xx][yy-1]>kk){
			bo[xx][yy-1]=1;
			q.push(mp(mp(xx,yy-1),mp(kk,zz)));
		}
		if(yy<n && c[xx][yy+1]!='T' && !bo[xx][yy+1] && zu[xx][yy+1]>kk){
			bo[xx][yy+1]=1;
			q.push(mp(mp(xx,yy+1),mp(kk,zz)));
		}
		q.pop();
	}
	if(bo[ax][ay]) return 1;
	return 0;
}
int main (){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c[i][j];
			if(c[i][j]=='M') x=i,y=j;
			if(c[i][j]=='D') ax=i,ay=j;
			zu[i][j]=1e9;
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(c[i][j]=='H') dfs(i,j);
	l=0,r=640000;
	while(l+1<r){
		ll mid=(l+r)/2;
		if(can(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
}

Subtask #1
11.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	2808 KB	Output isn't correct
2	Incorrect	8 ms	2936 KB	Output isn't correct
3	Incorrect	9 ms	3052 KB	Output isn't correct
4	Incorrect	9 ms	3220 KB	Output isn't correct
5	Correct	11 ms	3220 KB	Output is correct
6	Incorrect	11 ms	3220 KB	Output isn't correct
7	Execution timed out	1069 ms	7032 KB	Time limit exceeded
8	Incorrect	8 ms	7032 KB	Output isn't correct
9	Correct	11 ms	7032 KB	Output is correct
10	Incorrect	9 ms	7032 KB	Output isn't correct
11	Incorrect	11 ms	7032 KB	Output isn't correct
12	Incorrect	11 ms	7032 KB	Output isn't correct
13	Incorrect	38 ms	7032 KB	Output isn't correct
14	Incorrect	38 ms	7032 KB	Output isn't correct
15	Incorrect	8 ms	7032 KB	Output isn't correct
16	Correct	9 ms	7032 KB	Output is correct
17	Incorrect	8 ms	7032 KB	Output isn't correct
18	Correct	8 ms	7032 KB	Output is correct
19	Incorrect	7 ms	7032 KB	Output isn't correct
20	Correct	8 ms	7032 KB	Output is correct
21	Incorrect	11 ms	7032 KB	Output isn't correct
22	Correct	11 ms	7032 KB	Output is correct
23	Incorrect	8 ms	7032 KB	Output isn't correct
24	Correct	7 ms	7032 KB	Output is correct
25	Incorrect	10 ms	7032 KB	Output isn't correct
26	Correct	10 ms	7032 KB	Output is correct
27	Incorrect	9 ms	7032 KB	Output isn't correct
28	Correct	10 ms	7032 KB	Output is correct
29	Incorrect	9 ms	7032 KB	Output isn't correct
30	Correct	12 ms	7032 KB	Output is correct
31	Incorrect	10 ms	7032 KB	Output isn't correct
32	Correct	9 ms	7032 KB	Output is correct
33	Incorrect	22 ms	7032 KB	Output isn't correct
34	Correct	24 ms	7032 KB	Output is correct
35	Correct	55 ms	7032 KB	Output is correct
36	Incorrect	25 ms	7032 KB	Output isn't correct
37	Correct	36 ms	7032 KB	Output is correct
38	Correct	64 ms	7032 KB	Output is correct
39	Incorrect	32 ms	7032 KB	Output isn't correct
40	Correct	32 ms	7032 KB	Output is correct
41	Correct	87 ms	7288 KB	Output is correct
42	Incorrect	33 ms	7628 KB	Output isn't correct
43	Correct	51 ms	8000 KB	Output is correct
44	Correct	111 ms	8120 KB	Output is correct
45	Incorrect	36 ms	8756 KB	Output isn't correct
46	Correct	53 ms	8920 KB	Output is correct
47	Correct	127 ms	9316 KB	Output is correct
48	Incorrect	49 ms	9768 KB	Output isn't correct
49	Correct	52 ms	10120 KB	Output is correct
50	Correct	153 ms	10464 KB	Output is correct
51	Incorrect	54 ms	11092 KB	Output isn't correct
52	Correct	67 ms	11508 KB	Output is correct
53	Correct	178 ms	12052 KB	Output is correct
54	Incorrect	66 ms	12692 KB	Output isn't correct
55	Correct	66 ms	13076 KB	Output is correct
56	Correct	198 ms	13556 KB	Output is correct
57	Incorrect	72 ms	14420 KB	Output isn't correct
58	Correct	80 ms	14988 KB	Output is correct
59	Correct	263 ms	15668 KB	Output is correct
60	Incorrect	87 ms	16220 KB	Output isn't correct
61	Correct	98 ms	16852 KB	Output is correct
62	Correct	304 ms	17732 KB	Output is correct
63	Execution timed out	1079 ms	18104 KB	Time limit exceeded
64	Execution timed out	1069 ms	18860 KB	Time limit exceeded
65	Execution timed out	1073 ms	19376 KB	Time limit exceeded
66	Execution timed out	1082 ms	20136 KB	Time limit exceeded
67	Execution timed out	1080 ms	20768 KB	Time limit exceeded
68	Execution timed out	1079 ms	21300 KB	Time limit exceeded
69	Execution timed out	1074 ms	21936 KB	Time limit exceeded
70	Execution timed out	1039 ms	22708 KB	Time limit exceeded
71	Execution timed out	1079 ms	23292 KB	Time limit exceeded
72	Execution timed out	1084 ms	23792 KB	Time limit exceeded
73	Execution timed out	1083 ms	24420 KB	Time limit exceeded
74	Execution timed out	1067 ms	25176 KB	Time limit exceeded
75	Execution timed out	1069 ms	25780 KB	Time limit exceeded
76	Execution timed out	1060 ms	26304 KB	Time limit exceeded
77	Execution timed out	1081 ms	26932 KB	Time limit exceeded
78	Execution timed out	1085 ms	27560 KB	Time limit exceeded
79	Execution timed out	1058 ms	28200 KB	Time limit exceeded
80	Execution timed out	1069 ms	28820 KB	Time limit exceeded
81	Execution timed out	1087 ms	29572 KB	Time limit exceeded
82	Execution timed out	1075 ms	30076 KB	Time limit exceeded
83	Execution timed out	1073 ms	30832 KB	Time limit exceeded
84	Execution timed out	1076 ms	31460 KB	Time limit exceeded
85	Execution timed out	1084 ms	32088 KB	Time limit exceeded
86	Execution timed out	1065 ms	32708 KB	Time limit exceeded
87	Execution timed out	1064 ms	33492 KB	Time limit exceeded
88	Execution timed out	1068 ms	34116 KB	Time limit exceeded
89	Execution timed out	1078 ms	34648 KB	Time limit exceeded
90	Execution timed out	1073 ms	35236 KB	Time limit exceeded
91	Execution timed out	1035 ms	35904 KB	Time limit exceeded
92	Execution timed out	1071 ms	36660 KB	Time limit exceeded

답안 #65087

Compilation message

Subtask #1 11.0 / 100.0

Subtask #1
11.0 / 100.0