oj.uz

Submission #554937

# Submission time Handle Problem Language Result Execution time Memory
554937 2022-04-29T16:31:19 Z savackexp Mecho (IOI09_mecho) C++14
24 / 100
 283 ms 16760 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
typedef long long ll;
typedef long double ld;
const int MOD=1e9+7;
const int MAX=2e5+1;/*
ll  binpow(ll  a, ll  b) {
    ld  res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }

    return res;
}
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);
}
*/
ll n  , k ;
ll dx[]={0 , 0 , 1, -1};
ll dy[]={1 , -1 , 0, 0};
char grid[805][805];
ll vis[805][805];
ll levelm[805][805];
ll levelh[805][805];
vector<pair<ll,ll>>hive;
bool valid(ll x , ll y)
{
    return x>=0 && y>=0 && x<n && y<n && grid[x][y]!='H' && grid[x][y]!='T';
}
bool valid1(ll x , ll y)
{
    return x>=0 && y>=0 && x<n && y<n  && grid[x][y]!='T';
}
pair<ll,ll>m , d;
bool check(ll u)
{
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                levelm[i][j]=1e18;
            }
        }
        memset(vis , 0 ,sizeof vis );
        queue< pair<ll,ll> >q;
        q.push({m.fi,m.se});
        vis[m.fi][m.se]=1;
        levelm[m.fi][m.se]=0;
        while(!q.empty())
        {
            pair<ll,ll>p=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                ll nx = p.fi +  dx[i];
                ll ny = p.se +  dy[i];
                if(!valid(nx,ny))continue;
                levelm[nx][ny]=min(levelm[p.fi][p.se]+1 ,levelm[nx][ny]);
                ll qe = (levelm[nx][ny])/k + (levelm[nx][ny])%k!=0;
                if(levelh[nx][ny] <= qe + u )continue;
                if(vis[nx][ny])continue;

                vis[nx][ny] = 1;
                q.push({nx , ny});

            }

        }



    if(levelm[d.fi][d.se] != 1e18)
    {
        return true;
    }
    return false;
}

void bfs(vector<pair<ll,ll>>h)
{
    queue<pair<ll,ll> >q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            //levelh[i][j]=1e18;
        }
    }
    for(int i=0;i<h.size();i++)
    {
        levelh[h[i].fi][h[i].se]=0;
        vis[h[i].fi][h[i].se]=1;
        q.push(h[i]);
    }
    while(!q.empty())
    {
        pair<ll,ll>p=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {

            ll nx = p.fi + dx[i];
            ll ny = p.se + dy[i];
            if(!valid1(nx,ny))continue;
            if(vis[nx][ny])continue;
            levelh[nx][ny] = levelh[p.fi][p.se]+1;
            vis[nx][ny] = 1;
            q.push({nx , ny});
        }

    }
}





int main()
{

        fastio

        //freopen("gravity.in","r",stdin);
        //freopen("gravity.out","w",stdout);

        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            string s;
            cin>>s;
            for(int j=0;j<s.size();j++)
            {
                grid[i][j]=s[j];
                if(s[j]=='H')hive.pb({i,j});
                else if(s[j]=='M')m={i,j};
                else if(s[j]=='D')d={i,j};
            }
        }
        bfs(hive);
        memset(vis , 0 ,sizeof vis);
        ll l=0;
        ll r=1e7;
        ll ans=-1;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            if(check(mid))
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        //cout<<check(3)<<endl;
        cout<<ans<<endl;






































    return 0;
    }
/*
5 6
0 4 0
0 3 1
0 1 1
0 2 1
1 2 1
3 4 0

*/

Compilation message

mecho.cpp: In function 'void bfs(std::vector<std::pair<long long int, long long int> >)':
mecho.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=0;i<h.size();i++)
      |                 ~^~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:169:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |             for(int j=0;j<s.size();j++)
      |                         ~^~~~~~~~~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5332 KB Output is correct
2 Incorrect 7 ms 5336 KB Output isn't correct
3 Correct 6 ms 5368 KB Output is correct
4 Incorrect 6 ms 5408 KB Output isn't correct
5 Incorrect 7 ms 5460 KB Output isn't correct
6 Incorrect 10 ms 5460 KB Output isn't correct
7 Incorrect 202 ms 16324 KB Output isn't correct
8 Incorrect 6 ms 5464 KB Output isn't correct
9 Incorrect 7 ms 5464 KB Output isn't correct
10 Incorrect 7 ms 5540 KB Output isn't correct
11 Incorrect 6 ms 5464 KB Output isn't correct
12 Incorrect 6 ms 5972 KB Output isn't correct
13 Correct 7 ms 5844 KB Output is correct
14 Incorrect 7 ms 5972 KB Output isn't correct
15 Correct 6 ms 5460 KB Output is correct
16 Correct 7 ms 5588 KB Output is correct
17 Correct 7 ms 5588 KB Output is correct
18 Correct 19 ms 5640 KB Output is correct
19 Correct 15 ms 5588 KB Output is correct
20 Correct 7 ms 5588 KB Output is correct
21 Correct 7 ms 5792 KB Output is correct
22 Correct 6 ms 5716 KB Output is correct
23 Correct 9 ms 5844 KB Output is correct
24 Correct 7 ms 5844 KB Output is correct
25 Correct 16 ms 5972 KB Output is correct
26 Correct 6 ms 5972 KB Output is correct
27 Correct 17 ms 6036 KB Output is correct
28 Correct 7 ms 5972 KB Output is correct
29 Correct 7 ms 6056 KB Output is correct
30 Correct 7 ms 6000 KB Output is correct
31 Correct 6 ms 6100 KB Output is correct
32 Correct 7 ms 6100 KB Output is correct
33 Correct 17 ms 9696 KB Output is correct
34 Correct 23 ms 9936 KB Output is correct
35 Incorrect 47 ms 10068 KB Output isn't correct
36 Correct 19 ms 10308 KB Output is correct
37 Correct 19 ms 10620 KB Output is correct
38 Incorrect 65 ms 10708 KB Output isn't correct
39 Correct 33 ms 10836 KB Output is correct
40 Correct 23 ms 11336 KB Output is correct
41 Incorrect 76 ms 11348 KB Output isn't correct
42 Correct 28 ms 11476 KB Output is correct
43 Correct 27 ms 12012 KB Output is correct
44 Incorrect 110 ms 12064 KB Output isn't correct
45 Correct 33 ms 12116 KB Output is correct
46 Correct 31 ms 12628 KB Output is correct
47 Incorrect 110 ms 12784 KB Output isn't correct
48 Correct 34 ms 12748 KB Output is correct
49 Correct 34 ms 13268 KB Output is correct
50 Incorrect 132 ms 13452 KB Output isn't correct
51 Correct 36 ms 13296 KB Output is correct
52 Correct 39 ms 13928 KB Output is correct
53 Incorrect 171 ms 14132 KB Output isn't correct
54 Correct 44 ms 13908 KB Output is correct
55 Correct 41 ms 14496 KB Output is correct
56 Incorrect 196 ms 14792 KB Output isn't correct
57 Correct 51 ms 14540 KB Output is correct
58 Correct 47 ms 15112 KB Output is correct
59 Incorrect 231 ms 15480 KB Output isn't correct
60 Correct 60 ms 15188 KB Output is correct
61 Correct 50 ms 15680 KB Output is correct
62 Incorrect 283 ms 16028 KB Output isn't correct
63 Incorrect 173 ms 16076 KB Output isn't correct
64 Correct 217 ms 16076 KB Output is correct
65 Incorrect 216 ms 16148 KB Output isn't correct
66 Incorrect 169 ms 16140 KB Output isn't correct
67 Incorrect 250 ms 16140 KB Output isn't correct
68 Incorrect 85 ms 16196 KB Output isn't correct
69 Incorrect 82 ms 16136 KB Output isn't correct
70 Incorrect 81 ms 16200 KB Output isn't correct
71 Incorrect 92 ms 16192 KB Output isn't correct
72 Correct 63 ms 16184 KB Output is correct
73 Correct 97 ms 16716 KB Output is correct
74 Correct 117 ms 16760 KB Output is correct
75 Incorrect 133 ms 16680 KB Output isn't correct
76 Incorrect 118 ms 16680 KB Output isn't correct
77 Incorrect 129 ms 16756 KB Output isn't correct
78 Incorrect 162 ms 16704 KB Output isn't correct
79 Correct 99 ms 16680 KB Output is correct
80 Incorrect 91 ms 16596 KB Output isn't correct
81 Incorrect 132 ms 16668 KB Output isn't correct
82 Incorrect 129 ms 16688 KB Output isn't correct
83 Incorrect 192 ms 16408 KB Output isn't correct
84 Correct 143 ms 16596 KB Output is correct
85 Incorrect 129 ms 16584 KB Output isn't correct
86 Incorrect 155 ms 16584 KB Output isn't correct
87 Incorrect 165 ms 16588 KB Output isn't correct
88 Incorrect 185 ms 16372 KB Output isn't correct
89 Correct 178 ms 16468 KB Output is correct
90 Incorrect 186 ms 16464 KB Output isn't correct
91 Incorrect 206 ms 16556 KB Output isn't correct
92 Incorrect 172 ms 16468 KB Output isn't correct