| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 554797 |
2022-04-29T12:45:11 Z |
roctes7 |
Mecho (IOI09_mecho) |
C++17 |
|
509 ms |
31780 KB |
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define Endl "\n"
#define ENDL "\n"
#define fi first
#define se second
#define be begin()
#define en end()
#define pb push_back
#define mpa make_pair
typedef long long ll;
typedef long double ld;
const int MOD=1e9+7;
const int MAX=2e5+1;
ll n,s;
string arr[802][802];
bool vist[802][802];
ll mechoDist[802][802];
ll BeesDist[802][802];
pair<ll,ll> mecho;
pair<ll,ll> home;
ll dx[]={1,-1,0,0};
ll dy[]={0,0,1,-1};
bool valid (ll x,ll y){
return x>=1&&x<=n&&y>=1&&y<=n&&!vist[x][y]&&arr[x][y]!="T";
}
bool check =false;
void bfs (ll val){
vist[mecho.fi][mecho.se]=true;
queue<pair<ll,ll>>q;
q.push(mecho);
while (!q.empty()){
auto p =q.front();
ll x = p.fi;
ll y = p.se;
q.pop();
if(x==home.fi&&y==home.se)check=true;
for (int i=0;i<4;i++){
if(home.fi+dx[i]==x&&home.se+dy[i]==y)check=true;
}
if(val+mechoDist[x][y]>=BeesDist[x][y])continue;
for (ll i=0;i<4;i++){
ll nx = x+dx[i];
ll ny = y+dy[i];
if(valid(nx,ny)){
vist[nx][ny]=true;
q.push(mpa(nx,ny));
}
}
}
}
int main(){
fastio
//freopen("11.in","r",stdin);
//freopen("cl.out","w",stdout);
cin>>n>>s;
for (ll i=1;i<=n;i++){
string s;
cin>>s;
for (ll j=1;j<=n;j++){
arr[i][j]=s[j-1];
if(arr[i][j]=="M")mecho=mpa(i,j);
else if (arr[i][j]=="D")home = mpa(i,j);
}
}
queue <pair<ll,ll>> q;
q.push(mecho);
vist[mecho.fi][mecho.se]=true;
while(!q.empty()){
auto p = q.front();
ll x = p.fi;
ll y = p.se;
q.pop();
for (ll i=0;i<4;i++){
ll nx = x+dx[i];
ll ny = y+dy[i];
if(valid(nx,ny)&&arr[nx][ny]!="H"){
mechoDist[nx][ny]=mechoDist[x][y]+1;
vist[nx][ny]=true;
q.push(mpa(nx,ny));
}
}
}
for (ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){
mechoDist[i][j]=mechoDist[i][j]/s;
vist[i][j]=false;
}
for (ll i=1;i<=n;i++)for (ll j=1;j<=n;j++){
if(arr[i][j]=="H"){
q.push(mpa(i,j));
vist[i][j]=true;
}
}
while(!q.empty()){
auto p = q.front();
ll x = p.fi;
ll y = p.se;
q.pop();
for (ll i=0;i<4;i++){
ll nx = x+dx[i];
ll ny = y+dy[i];
if(valid(nx,ny)&&arr[nx][ny]!="D"&&arr[nx][ny]!="H"){
BeesDist[nx][ny]=BeesDist[x][y]+1;
vist[nx][ny]=true;
q.push(mpa(nx,ny));
}
}
}
/*cout<<endl<<endl;
for(ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){
if(arr[i][j]=="G")
cout<<mechoDist[i][j];
else cout<<arr[i][j];
}
cout<<endl;
}
cout<<endl<<endl;
for(ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){
cout<<BeesDist[i][j];
}
cout<<endl;
}*/
ll l=0;
ll r = 1e9;
ll ans =-1;
while (l<=r){
ll mid = (l+r)/2;
for (ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){
vist[i][j]=false;
}
check=false;
bfs(mid);
if(check){
l=mid+1;
ans = mid;
} else {
r=mid-1;
}
}
cout<<ans;
return 0;
}
unsigned long long power(unsigned long long x,
ll y, ll p)
{
unsigned long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
unsigned long long modInverse(unsigned long long n,
ll p)
{
return power(n, p - 2, p);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
20436 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
20436 KB |
Output isn't correct |
| 3 |
Correct |
10 ms |
20472 KB |
Output is correct |
| 4 |
Correct |
11 ms |
20436 KB |
Output is correct |
| 5 |
Correct |
10 ms |
20436 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
20464 KB |
Output isn't correct |
| 7 |
Incorrect |
349 ms |
31276 KB |
Output isn't correct |
| 8 |
Correct |
11 ms |
20564 KB |
Output is correct |
| 9 |
Correct |
11 ms |
20564 KB |
Output is correct |
| 10 |
Correct |
10 ms |
20524 KB |
Output is correct |
| 11 |
Correct |
10 ms |
20692 KB |
Output is correct |
| 12 |
Incorrect |
12 ms |
20948 KB |
Output isn't correct |
| 13 |
Correct |
13 ms |
20948 KB |
Output is correct |
| 14 |
Correct |
11 ms |
20948 KB |
Output is correct |
| 15 |
Incorrect |
11 ms |
20564 KB |
Output isn't correct |
| 16 |
Incorrect |
11 ms |
20564 KB |
Output isn't correct |
| 17 |
Incorrect |
10 ms |
20692 KB |
Output isn't correct |
| 18 |
Incorrect |
10 ms |
20652 KB |
Output isn't correct |
| 19 |
Incorrect |
11 ms |
20692 KB |
Output isn't correct |
| 20 |
Incorrect |
11 ms |
20692 KB |
Output isn't correct |
| 21 |
Incorrect |
11 ms |
20820 KB |
Output isn't correct |
| 22 |
Incorrect |
13 ms |
20820 KB |
Output isn't correct |
| 23 |
Incorrect |
12 ms |
20944 KB |
Output isn't correct |
| 24 |
Incorrect |
11 ms |
20948 KB |
Output isn't correct |
| 25 |
Incorrect |
11 ms |
20948 KB |
Output isn't correct |
| 26 |
Incorrect |
13 ms |
20948 KB |
Output isn't correct |
| 27 |
Incorrect |
12 ms |
21076 KB |
Output isn't correct |
| 28 |
Incorrect |
11 ms |
21036 KB |
Output isn't correct |
| 29 |
Incorrect |
11 ms |
21080 KB |
Output isn't correct |
| 30 |
Incorrect |
11 ms |
21056 KB |
Output isn't correct |
| 31 |
Incorrect |
11 ms |
21204 KB |
Output isn't correct |
| 32 |
Incorrect |
12 ms |
21180 KB |
Output isn't correct |
| 33 |
Incorrect |
31 ms |
24628 KB |
Output isn't correct |
| 34 |
Incorrect |
30 ms |
24892 KB |
Output isn't correct |
| 35 |
Incorrect |
81 ms |
25128 KB |
Output isn't correct |
| 36 |
Incorrect |
32 ms |
25320 KB |
Output isn't correct |
| 37 |
Incorrect |
31 ms |
25604 KB |
Output isn't correct |
| 38 |
Incorrect |
106 ms |
25804 KB |
Output isn't correct |
| 39 |
Incorrect |
36 ms |
25972 KB |
Output isn't correct |
| 40 |
Incorrect |
38 ms |
26380 KB |
Output isn't correct |
| 41 |
Incorrect |
126 ms |
26472 KB |
Output isn't correct |
| 42 |
Incorrect |
38 ms |
26576 KB |
Output isn't correct |
| 43 |
Incorrect |
38 ms |
26988 KB |
Output isn't correct |
| 44 |
Incorrect |
179 ms |
27152 KB |
Output isn't correct |
| 45 |
Incorrect |
48 ms |
27068 KB |
Output isn't correct |
| 46 |
Incorrect |
49 ms |
27740 KB |
Output isn't correct |
| 47 |
Incorrect |
196 ms |
27848 KB |
Output isn't correct |
| 48 |
Incorrect |
51 ms |
27736 KB |
Output isn't correct |
| 49 |
Incorrect |
58 ms |
28300 KB |
Output isn't correct |
| 50 |
Incorrect |
247 ms |
28492 KB |
Output isn't correct |
| 51 |
Incorrect |
58 ms |
28404 KB |
Output isn't correct |
| 52 |
Incorrect |
65 ms |
28876 KB |
Output isn't correct |
| 53 |
Incorrect |
275 ms |
29172 KB |
Output isn't correct |
| 54 |
Incorrect |
82 ms |
28932 KB |
Output isn't correct |
| 55 |
Incorrect |
79 ms |
29564 KB |
Output isn't correct |
| 56 |
Incorrect |
314 ms |
29884 KB |
Output isn't correct |
| 57 |
Incorrect |
69 ms |
29532 KB |
Output isn't correct |
| 58 |
Incorrect |
80 ms |
30208 KB |
Output isn't correct |
| 59 |
Incorrect |
370 ms |
30504 KB |
Output isn't correct |
| 60 |
Incorrect |
81 ms |
30196 KB |
Output isn't correct |
| 61 |
Incorrect |
88 ms |
30624 KB |
Output isn't correct |
| 62 |
Incorrect |
434 ms |
31048 KB |
Output isn't correct |
| 63 |
Correct |
325 ms |
31120 KB |
Output is correct |
| 64 |
Correct |
509 ms |
31140 KB |
Output is correct |
| 65 |
Correct |
477 ms |
31160 KB |
Output is correct |
| 66 |
Correct |
368 ms |
31164 KB |
Output is correct |
| 67 |
Correct |
327 ms |
31128 KB |
Output is correct |
| 68 |
Correct |
182 ms |
31180 KB |
Output is correct |
| 69 |
Correct |
183 ms |
31220 KB |
Output is correct |
| 70 |
Correct |
151 ms |
31180 KB |
Output is correct |
| 71 |
Correct |
151 ms |
31096 KB |
Output is correct |
| 72 |
Correct |
138 ms |
31100 KB |
Output is correct |
| 73 |
Correct |
189 ms |
31744 KB |
Output is correct |
| 74 |
Incorrect |
212 ms |
31616 KB |
Output isn't correct |
| 75 |
Incorrect |
252 ms |
31608 KB |
Output isn't correct |
| 76 |
Incorrect |
223 ms |
31780 KB |
Output isn't correct |
| 77 |
Incorrect |
240 ms |
31696 KB |
Output isn't correct |
| 78 |
Correct |
232 ms |
31644 KB |
Output is correct |
| 79 |
Incorrect |
226 ms |
31740 KB |
Output isn't correct |
| 80 |
Incorrect |
207 ms |
31632 KB |
Output isn't correct |
| 81 |
Incorrect |
255 ms |
31632 KB |
Output isn't correct |
| 82 |
Incorrect |
227 ms |
31572 KB |
Output isn't correct |
| 83 |
Incorrect |
295 ms |
31556 KB |
Output isn't correct |
| 84 |
Incorrect |
274 ms |
31648 KB |
Output isn't correct |
| 85 |
Incorrect |
269 ms |
31476 KB |
Output isn't correct |
| 86 |
Incorrect |
300 ms |
31436 KB |
Output isn't correct |
| 87 |
Incorrect |
303 ms |
31556 KB |
Output isn't correct |
| 88 |
Incorrect |
314 ms |
31464 KB |
Output isn't correct |
| 89 |
Incorrect |
325 ms |
31488 KB |
Output isn't correct |
| 90 |
Incorrect |
321 ms |
31436 KB |
Output isn't correct |
| 91 |
Incorrect |
322 ms |
31568 KB |
Output isn't correct |
| 92 |
Incorrect |
320 ms |
31360 KB |
Output isn't correct |
