oj.uz

답안 #522410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522410 2022-02-04T22:51:54 Z AndresTL Mecho (IOI09_mecho) C++11
39 / 100
 160 ms 6360 KB 
#include<iostream>
#include<utility>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
int n,s;
char mapa[802][802];
int colmena[802][802];
int mecho[802][802];
int mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool abeja(int i, int j){
	if(i<0 || i>n || j<0 || j>n) return 0;
	if(colmena[i][j]!=-1) return 0;
	if(mapa[i][j]=='T' && mapa[i][j]=='D') return 0;
	return 1;
}
void BFScolmena(){
	queue<pair<int,int>> q;
	pair<int,int> dad, son;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mapa[i][j]=='H'){
				q.push(make_pair(i,j));
				colmena[i][j]=0;
			}	
		}
	}
	while(!q.empty()){
		dad=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			son=make_pair(dad.fi+mov[i][0],dad.se+mov[i][1]);
			if(!abeja(son.first,son.second))continue;
			colmena[son.fi][son.se]=colmena[dad.fi][dad.se]+1;
			q.push(son);
		}
	}
}
int i1,i2,j1,j2;
bool paso(int i,int j,int time){
	if(i<0 || i>n || j<0 || j>n) return 0;
	if(mecho[i][j]!=-1) return 0;
	if(mapa[i][j]=='T') return 0;
	if(mapa[i][j]=='D') return 1;
	if(time>=colmena[i][j]) return 0;
	return 1;
}
bool BFSmecho(int t){
	queue<pair<int,int>> q;
	pair<int,int>dad,son;
	int time;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			mecho[i][j]=-1;
		}
	}
	mecho[i1][j1]=0;
	if(t>=colmena[i1][j1]) return 0;
	q.push(make_pair(i1,j1));
	while(!q.empty()){
		dad=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			son=make_pair(dad.fi+mov[i][0],dad.se+mov[i][1]);
			time=t+(mecho[dad.fi][dad.se]+1)/s;
			if(!paso(son.fi,son.se,time)) continue;
			mecho[son.fi][son.se]=mecho[dad.fi][dad.se]+1;
			q.push(son);
		}
	}
	return mecho[i2][j2]!=-1;
}
int main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			colmena[i][j]=-1;
			cin>>mapa[i][j];
			if(mapa[i][j]=='M'){i1=i;j1=j;}
			if(mapa[i][j]=='D'){i2=i;j2=j;}			
		}
	}
	BFScolmena();
	int l=0,r=n*n,m;
	int res=-1;
	while(l<=r){
		m =(l+r)/2;
		if(BFSmecho(m)){
			res=m;
			l=m+1;
		}else{
			r=m-1;
		}
	}
	cout<<res<<'\n';
}

Subtask #1
39.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 300 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 109 ms 6340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Incorrect 0 ms 332 KB Output isn't correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 1 ms 716 KB Output isn't correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Incorrect 1 ms 460 KB Output isn't correct
16 Incorrect 1 ms 460 KB Output isn't correct
17 Incorrect 1 ms 460 KB Output isn't correct
18 Incorrect 1 ms 460 KB Output isn't correct
19 Incorrect 1 ms 460 KB Output isn't correct
20 Incorrect 1 ms 460 KB Output isn't correct
21 Incorrect 1 ms 588 KB Output isn't correct
22 Incorrect 1 ms 588 KB Output isn't correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Incorrect 1 ms 588 KB Output isn't correct
25 Incorrect 1 ms 716 KB Output isn't correct
26 Incorrect 1 ms 716 KB Output isn't correct
27 Incorrect 1 ms 716 KB Output isn't correct
28 Incorrect 1 ms 716 KB Output isn't correct
29 Incorrect 1 ms 716 KB Output isn't correct
30 Incorrect 1 ms 716 KB Output isn't correct
31 Incorrect 1 ms 844 KB Output isn't correct
32 Incorrect 1 ms 844 KB Output isn't correct
33 Incorrect 12 ms 2764 KB Output isn't correct
34 Incorrect 11 ms 2708 KB Output isn't correct
35 Correct 25 ms 2752 KB Output is correct
36 Incorrect 13 ms 3108 KB Output isn't correct
37 Incorrect 16 ms 3036 KB Output isn't correct
38 Correct 33 ms 3024 KB Output is correct
39 Incorrect 15 ms 3404 KB Output isn't correct
40 Incorrect 16 ms 3448 KB Output isn't correct
41 Correct 42 ms 3368 KB Output is correct
42 Incorrect 19 ms 3788 KB Output isn't correct
43 Incorrect 20 ms 3816 KB Output isn't correct
44 Correct 54 ms 3816 KB Output is correct
45 Incorrect 25 ms 4172 KB Output isn't correct
46 Incorrect 30 ms 4164 KB Output isn't correct
47 Correct 58 ms 4180 KB Output is correct
48 Incorrect 27 ms 4496 KB Output isn't correct
49 Incorrect 29 ms 4540 KB Output isn't correct
50 Correct 69 ms 4420 KB Output is correct
51 Incorrect 34 ms 4812 KB Output isn't correct
52 Incorrect 33 ms 4812 KB Output isn't correct
53 Correct 93 ms 4896 KB Output is correct
54 Incorrect 38 ms 5172 KB Output isn't correct
55 Incorrect 39 ms 5188 KB Output isn't correct
56 Correct 102 ms 5216 KB Output is correct
57 Incorrect 42 ms 5484 KB Output isn't correct
58 Incorrect 44 ms 5592 KB Output isn't correct
59 Correct 125 ms 5596 KB Output is correct
60 Incorrect 48 ms 5876 KB Output isn't correct
61 Incorrect 49 ms 5828 KB Output isn't correct
62 Correct 136 ms 5944 KB Output is correct
63 Incorrect 49 ms 5888 KB Output isn't correct
64 Incorrect 160 ms 5840 KB Output isn't correct
65 Incorrect 127 ms 5944 KB Output isn't correct
66 Incorrect 51 ms 5828 KB Output isn't correct
67 Correct 64 ms 5856 KB Output is correct
68 Incorrect 50 ms 6096 KB Output isn't correct
69 Incorrect 56 ms 6048 KB Output isn't correct
70 Incorrect 49 ms 6008 KB Output isn't correct
71 Incorrect 58 ms 6084 KB Output isn't correct
72 Incorrect 51 ms 6016 KB Output isn't correct
73 Correct 56 ms 6168 KB Output is correct
74 Correct 74 ms 6212 KB Output is correct
75 Correct 90 ms 6096 KB Output is correct
76 Correct 81 ms 6184 KB Output is correct
77 Correct 87 ms 6360 KB Output is correct
78 Correct 95 ms 6096 KB Output is correct
79 Correct 66 ms 6084 KB Output is correct
80 Correct 79 ms 6084 KB Output is correct
81 Correct 101 ms 6116 KB Output is correct
82 Correct 100 ms 6172 KB Output is correct
83 Correct 111 ms 6068 KB Output is correct
84 Correct 84 ms 6096 KB Output is correct
85 Correct 93 ms 6028 KB Output is correct
86 Correct 103 ms 6064 KB Output is correct
87 Correct 96 ms 6148 KB Output is correct
88 Correct 98 ms 6052 KB Output is correct
89 Correct 92 ms 6044 KB Output is correct
90 Correct 98 ms 5992 KB Output is correct
91 Correct 96 ms 6080 KB Output is correct
92 Correct 113 ms 6036 KB Output is correct