oj.uz

Submission #554934

# Submission time Handle Problem Language Result Execution time Memory
554934 2022-04-29T16:26:58 Z savackexp Mecho (IOI09_mecho) C++14
24 / 100
 220 ms 17484 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]=-1;
            }
        }
        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;
                ll qe = (levelm[p.fi][p.se]+1)/k + (levelm[p.fi][p.se]+1)%k!=0;
                if(levelh[nx][ny] <= qe + u )continue;
                if(vis[nx][ny])continue;
                levelm[nx][ny]=levelm[p.fi][p.se]+1;
                vis[nx][ny] = 1;
                q.push({nx , ny});

            }

        }



    if(levelm[d.fi][d.se] != -1)
    {
        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 6 ms 5332 KB Output is correct
2 Incorrect 6 ms 5448 KB Output isn't correct
3 Correct 6 ms 5332 KB Output is correct
4 Incorrect 6 ms 5332 KB Output isn't correct
5 Incorrect 6 ms 5444 KB Output isn't correct
6 Incorrect 7 ms 5460 KB Output isn't correct
7 Incorrect 161 ms 17024 KB Output isn't correct
8 Incorrect 6 ms 5460 KB Output isn't correct
9 Incorrect 6 ms 5460 KB Output isn't correct
10 Incorrect 6 ms 5460 KB Output isn't correct
11 Incorrect 7 ms 5444 KB Output isn't correct
12 Incorrect 7 ms 5972 KB Output isn't correct
13 Correct 6 ms 5832 KB Output is correct
14 Incorrect 7 ms 6004 KB Output isn't correct
15 Correct 7 ms 5588 KB Output is correct
16 Correct 7 ms 5588 KB Output is correct
17 Correct 7 ms 5588 KB Output is correct
18 Correct 7 ms 5640 KB Output is correct
19 Correct 6 ms 5588 KB Output is correct
20 Correct 6 ms 5588 KB Output is correct
21 Correct 7 ms 5716 KB Output is correct
22 Correct 6 ms 5708 KB Output is correct
23 Correct 6 ms 5844 KB Output is correct
24 Correct 6 ms 5844 KB Output is correct
25 Correct 6 ms 5988 KB Output is correct
26 Correct 7 ms 5964 KB Output is correct
27 Correct 6 ms 5964 KB Output is correct
28 Correct 6 ms 5972 KB Output is correct
29 Correct 6 ms 6096 KB Output is correct
30 Correct 8 ms 5992 KB Output is correct
31 Correct 7 ms 6096 KB Output is correct
32 Correct 11 ms 6224 KB Output is correct
33 Correct 14 ms 9816 KB Output is correct
34 Correct 13 ms 9928 KB Output is correct
35 Incorrect 34 ms 10196 KB Output isn't correct
36 Correct 14 ms 10396 KB Output is correct
37 Correct 16 ms 10688 KB Output is correct
38 Incorrect 48 ms 10836 KB Output isn't correct
39 Correct 22 ms 11092 KB Output is correct
40 Correct 19 ms 11520 KB Output is correct
41 Incorrect 64 ms 11636 KB Output isn't correct
42 Correct 30 ms 11768 KB Output is correct
43 Correct 24 ms 12244 KB Output is correct
44 Incorrect 73 ms 12352 KB Output isn't correct
45 Correct 31 ms 12364 KB Output is correct
46 Correct 25 ms 12884 KB Output is correct
47 Incorrect 83 ms 13080 KB Output isn't correct
48 Correct 30 ms 13004 KB Output is correct
49 Correct 32 ms 13708 KB Output is correct
50 Incorrect 101 ms 13812 KB Output isn't correct
51 Correct 30 ms 13772 KB Output is correct
52 Correct 34 ms 14368 KB Output is correct
53 Incorrect 129 ms 14548 KB Output isn't correct
54 Correct 37 ms 14412 KB Output is correct
55 Correct 37 ms 15000 KB Output is correct
56 Incorrect 155 ms 15336 KB Output isn't correct
57 Correct 42 ms 15144 KB Output is correct
58 Correct 39 ms 15576 KB Output is correct
59 Incorrect 170 ms 15944 KB Output isn't correct
60 Correct 40 ms 15820 KB Output is correct
61 Correct 40 ms 16268 KB Output is correct
62 Incorrect 193 ms 16764 KB Output isn't correct
63 Incorrect 158 ms 16832 KB Output isn't correct
64 Correct 198 ms 16700 KB Output is correct
65 Incorrect 192 ms 16768 KB Output isn't correct
66 Incorrect 153 ms 16688 KB Output isn't correct
67 Incorrect 220 ms 16840 KB Output isn't correct
68 Incorrect 76 ms 16836 KB Output isn't correct
69 Incorrect 74 ms 16828 KB Output isn't correct
70 Incorrect 74 ms 16748 KB Output isn't correct
71 Incorrect 76 ms 16828 KB Output isn't correct
72 Correct 57 ms 16760 KB Output is correct
73 Correct 81 ms 17372 KB Output is correct
74 Correct 92 ms 17356 KB Output is correct
75 Incorrect 100 ms 17384 KB Output isn't correct
76 Incorrect 92 ms 17484 KB Output isn't correct
77 Incorrect 100 ms 17312 KB Output isn't correct
78 Incorrect 118 ms 17252 KB Output isn't correct
79 Correct 78 ms 17160 KB Output is correct
80 Incorrect 79 ms 17092 KB Output isn't correct
81 Incorrect 97 ms 17172 KB Output isn't correct
82 Incorrect 90 ms 17240 KB Output isn't correct
83 Incorrect 125 ms 17040 KB Output isn't correct
84 Correct 107 ms 17020 KB Output is correct
85 Incorrect 102 ms 16936 KB Output isn't correct
86 Incorrect 117 ms 16828 KB Output isn't correct
87 Incorrect 124 ms 16828 KB Output isn't correct
88 Incorrect 128 ms 16588 KB Output isn't correct
89 Correct 129 ms 16612 KB Output is correct
90 Incorrect 136 ms 16712 KB Output isn't correct
91 Incorrect 130 ms 16708 KB Output isn't correct
92 Incorrect 127 ms 16688 KB Output isn't correct