oj.uz

Submission #554804

# Submission time Handle Problem Language Result Execution time Memory
554804 2022-04-29T12:55:06 Z roctes7 Mecho (IOI09_mecho) C++17
4 / 100
 487 ms 31764 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 (ll i=0;i<4;i++){
        ll nx = x+dx[i];
        ll ny = y+dy[i];

        if(valid(nx,ny)&&val + mechoDist[nx][ny]>BeesDist[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 (int i=1;i<=n;i++)for (int j=1;j<=n;j++){
    BeesDist[i][j]=1e9;
    mechoDist[i][j]=1e9;
}

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);
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 20436 KB Output isn't correct
2 Incorrect 11 ms 20484 KB Output isn't correct
3 Incorrect 10 ms 20516 KB Output isn't correct
4 Incorrect 11 ms 20528 KB Output isn't correct
5 Incorrect 10 ms 20436 KB Output isn't correct
6 Incorrect 11 ms 20552 KB Output isn't correct
7 Incorrect 143 ms 31288 KB Output isn't correct
8 Incorrect 10 ms 20564 KB Output isn't correct
9 Incorrect 11 ms 20600 KB Output isn't correct
10 Incorrect 11 ms 20660 KB Output isn't correct
11 Incorrect 10 ms 20564 KB Output isn't correct
12 Incorrect 13 ms 21040 KB Output isn't correct
13 Incorrect 11 ms 20948 KB Output isn't correct
14 Correct 13 ms 21080 KB Output is correct
15 Incorrect 11 ms 20612 KB Output isn't correct
16 Incorrect 11 ms 20660 KB Output isn't correct
17 Incorrect 10 ms 20692 KB Output isn't correct
18 Incorrect 10 ms 20692 KB Output isn't correct
19 Incorrect 11 ms 20692 KB Output isn't correct
20 Incorrect 10 ms 20692 KB Output isn't correct
21 Incorrect 12 ms 20820 KB Output isn't correct
22 Incorrect 12 ms 20824 KB Output isn't correct
23 Incorrect 12 ms 20960 KB Output isn't correct
24 Incorrect 11 ms 20944 KB Output isn't correct
25 Incorrect 13 ms 20948 KB Output isn't correct
26 Incorrect 11 ms 21068 KB Output isn't correct
27 Incorrect 13 ms 21076 KB Output isn't correct
28 Incorrect 11 ms 21076 KB Output isn't correct
29 Incorrect 16 ms 21172 KB Output isn't correct
30 Incorrect 11 ms 21168 KB Output isn't correct
31 Incorrect 14 ms 21204 KB Output isn't correct
32 Incorrect 11 ms 21204 KB Output isn't correct
33 Incorrect 104 ms 25136 KB Output isn't correct
34 Incorrect 28 ms 25044 KB Output isn't correct
35 Incorrect 32 ms 25136 KB Output isn't correct
36 Incorrect 149 ms 25812 KB Output isn't correct
37 Incorrect 33 ms 25812 KB Output isn't correct
38 Incorrect 39 ms 25756 KB Output isn't correct
39 Incorrect 181 ms 26480 KB Output isn't correct
40 Incorrect 34 ms 26392 KB Output isn't correct
41 Incorrect 50 ms 26444 KB Output isn't correct
42 Incorrect 234 ms 27144 KB Output isn't correct
43 Incorrect 42 ms 27128 KB Output isn't correct
44 Incorrect 58 ms 27152 KB Output isn't correct
45 Incorrect 251 ms 27912 KB Output isn't correct
46 Incorrect 47 ms 27712 KB Output isn't correct
47 Incorrect 66 ms 27828 KB Output isn't correct
48 Incorrect 282 ms 28488 KB Output isn't correct
49 Incorrect 53 ms 28484 KB Output isn't correct
50 Incorrect 86 ms 28392 KB Output isn't correct
51 Incorrect 354 ms 29160 KB Output isn't correct
52 Incorrect 63 ms 29152 KB Output isn't correct
53 Incorrect 98 ms 29156 KB Output isn't correct
54 Incorrect 392 ms 29824 KB Output isn't correct
55 Incorrect 78 ms 29828 KB Output isn't correct
56 Incorrect 109 ms 29744 KB Output isn't correct
57 Incorrect 419 ms 30424 KB Output isn't correct
58 Incorrect 73 ms 30488 KB Output isn't correct
59 Incorrect 134 ms 30500 KB Output isn't correct
60 Incorrect 487 ms 31048 KB Output isn't correct
61 Incorrect 84 ms 31156 KB Output isn't correct
62 Incorrect 137 ms 31168 KB Output isn't correct
63 Incorrect 139 ms 31052 KB Output isn't correct
64 Incorrect 138 ms 31072 KB Output isn't correct
65 Incorrect 135 ms 31164 KB Output isn't correct
66 Incorrect 136 ms 31056 KB Output isn't correct
67 Correct 142 ms 31044 KB Output is correct
68 Incorrect 152 ms 31216 KB Output isn't correct
69 Incorrect 145 ms 31168 KB Output isn't correct
70 Incorrect 151 ms 31248 KB Output isn't correct
71 Incorrect 147 ms 31180 KB Output isn't correct
72 Incorrect 150 ms 31216 KB Output isn't correct
73 Incorrect 154 ms 31704 KB Output isn't correct
74 Incorrect 185 ms 31764 KB Output isn't correct
75 Incorrect 170 ms 31676 KB Output isn't correct
76 Incorrect 163 ms 31704 KB Output isn't correct
77 Incorrect 192 ms 31708 KB Output isn't correct
78 Correct 164 ms 31672 KB Output is correct
79 Incorrect 154 ms 31752 KB Output isn't correct
80 Incorrect 162 ms 31568 KB Output isn't correct
81 Incorrect 165 ms 31548 KB Output isn't correct
82 Incorrect 171 ms 31540 KB Output isn't correct
83 Incorrect 173 ms 31580 KB Output isn't correct
84 Incorrect 194 ms 31640 KB Output isn't correct
85 Incorrect 183 ms 31552 KB Output isn't correct
86 Incorrect 163 ms 31540 KB Output isn't correct
87 Incorrect 171 ms 31564 KB Output isn't correct
88 Incorrect 183 ms 31476 KB Output isn't correct
89 Incorrect 164 ms 31484 KB Output isn't correct
90 Incorrect 170 ms 31412 KB Output isn't correct
91 Incorrect 183 ms 31480 KB Output isn't correct
92 Incorrect 184 ms 31480 KB Output isn't correct