Submission #555448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555448	2022-04-30T23:52:06 Z	savackexp	Mecho (IOI09_mecho)	C++14	22 / 100	288 ms	16796 KB

mecho

#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' && grid[x][y]!='D'  && grid[x][y]!='M';
}
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;
        if(u >= levelh[m.fi][m.se])return false;
        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] - u <= qe)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;
            levelh[nx][ny] = min(levelh[p.fi][p.se]+1 ,levelh[nx][ny]);
            if(vis[nx][ny])continue;
            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=1e18;
        ll ans=-1;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            if(check(mid))
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        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:126: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]
  126 |     for(int i=0;i<h.size();i++)
      |                 ~^~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:168:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for(int j=0;j<s.size();j++)
      |                         ~^~~~~~~~~

Subtask #1

22.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	5436 KB	Output is correct
2	Correct	10 ms	5436 KB	Output is correct
3	Correct	11 ms	5444 KB	Output is correct
4	Correct	11 ms	5448 KB	Output is correct
5	Incorrect	12 ms	5472 KB	Output isn't correct
6	Incorrect	11 ms	5460 KB	Output isn't correct
7	Incorrect	227 ms	16248 KB	Output isn't correct
8	Correct	10 ms	5544 KB	Output is correct
9	Incorrect	11 ms	5460 KB	Output isn't correct
10	Incorrect	11 ms	5460 KB	Output isn't correct
11	Incorrect	10 ms	5460 KB	Output isn't correct
12	Incorrect	10 ms	5972 KB	Output isn't correct
13	Correct	12 ms	5844 KB	Output is correct
14	Correct	11 ms	6004 KB	Output is correct
15	Correct	10 ms	5592 KB	Output is correct
16	Incorrect	10 ms	5588 KB	Output isn't correct
17	Correct	11 ms	5588 KB	Output is correct
18	Incorrect	11 ms	5644 KB	Output isn't correct
19	Correct	11 ms	5712 KB	Output is correct
20	Incorrect	10 ms	5712 KB	Output isn't correct
21	Correct	10 ms	5716 KB	Output is correct
22	Incorrect	11 ms	5716 KB	Output isn't correct
23	Correct	12 ms	5896 KB	Output is correct
24	Incorrect	11 ms	5904 KB	Output isn't correct
25	Correct	11 ms	5988 KB	Output is correct
26	Incorrect	12 ms	5996 KB	Output isn't correct
27	Correct	10 ms	5972 KB	Output is correct
28	Incorrect	13 ms	5972 KB	Output isn't correct
29	Correct	13 ms	6100 KB	Output is correct
30	Incorrect	11 ms	6108 KB	Output isn't correct
31	Correct	13 ms	6148 KB	Output is correct
32	Incorrect	11 ms	6100 KB	Output isn't correct
33	Correct	26 ms	10096 KB	Output is correct
34	Incorrect	26 ms	10196 KB	Output isn't correct
35	Incorrect	56 ms	10016 KB	Output isn't correct
36	Correct	29 ms	10708 KB	Output is correct
37	Incorrect	31 ms	10720 KB	Output isn't correct
38	Incorrect	70 ms	10752 KB	Output isn't correct
39	Correct	36 ms	11428 KB	Output is correct
40	Incorrect	45 ms	11380 KB	Output isn't correct
41	Incorrect	102 ms	11436 KB	Output isn't correct
42	Correct	40 ms	12092 KB	Output is correct
43	Incorrect	44 ms	12116 KB	Output isn't correct
44	Incorrect	110 ms	12108 KB	Output isn't correct
45	Correct	55 ms	12756 KB	Output is correct
46	Incorrect	53 ms	12784 KB	Output isn't correct
47	Incorrect	133 ms	12724 KB	Output isn't correct
48	Correct	57 ms	13396 KB	Output is correct
49	Incorrect	57 ms	13420 KB	Output isn't correct
50	Incorrect	170 ms	13444 KB	Output isn't correct
51	Correct	66 ms	14036 KB	Output is correct
52	Incorrect	65 ms	14124 KB	Output isn't correct
53	Incorrect	223 ms	14136 KB	Output isn't correct
54	Correct	70 ms	14780 KB	Output is correct
55	Incorrect	67 ms	14776 KB	Output isn't correct
56	Incorrect	219 ms	14796 KB	Output isn't correct
57	Correct	84 ms	15444 KB	Output is correct
58	Incorrect	78 ms	15564 KB	Output isn't correct
59	Incorrect	266 ms	15476 KB	Output isn't correct
60	Correct	82 ms	16084 KB	Output is correct
61	Incorrect	82 ms	16128 KB	Output isn't correct
62	Incorrect	288 ms	16140 KB	Output isn't correct
63	Incorrect	164 ms	16136 KB	Output isn't correct
64	Incorrect	271 ms	16140 KB	Output isn't correct
65	Incorrect	260 ms	16144 KB	Output isn't correct
66	Correct	197 ms	16140 KB	Output is correct
67	Correct	178 ms	16140 KB	Output is correct
68	Incorrect	110 ms	16196 KB	Output isn't correct
69	Incorrect	121 ms	16128 KB	Output isn't correct
70	Incorrect	99 ms	16076 KB	Output isn't correct
71	Incorrect	100 ms	16076 KB	Output isn't correct
72	Incorrect	111 ms	16204 KB	Output isn't correct
73	Incorrect	173 ms	16716 KB	Output isn't correct
74	Incorrect	160 ms	16648 KB	Output isn't correct
75	Incorrect	193 ms	16716 KB	Output isn't correct
76	Incorrect	155 ms	16772 KB	Output isn't correct
77	Incorrect	162 ms	16740 KB	Output isn't correct
78	Correct	172 ms	16796 KB	Output is correct
79	Incorrect	151 ms	16588 KB	Output isn't correct
80	Incorrect	157 ms	16688 KB	Output isn't correct
81	Incorrect	170 ms	16680 KB	Output isn't correct
82	Incorrect	153 ms	16688 KB	Output isn't correct
83	Incorrect	193 ms	16532 KB	Output isn't correct
84	Incorrect	189 ms	16716 KB	Output isn't correct
85	Incorrect	185 ms	16596 KB	Output isn't correct
86	Incorrect	216 ms	16588 KB	Output isn't correct
87	Incorrect	195 ms	16588 KB	Output isn't correct
88	Incorrect	190 ms	16440 KB	Output isn't correct
89	Incorrect	216 ms	16448 KB	Output isn't correct
90	Incorrect	231 ms	16472 KB	Output isn't correct
91	Incorrect	221 ms	16468 KB	Output isn't correct
92	Incorrect	216 ms	16400 KB	Output isn't correct