Submission #555604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555604	2022-05-01T08:56:59 Z	savackexp	Mecho (IOI09_mecho)	C++14	100 / 100	301 ms	17392 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';
}
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;
                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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	5332 KB	Output is correct
2	Correct	10 ms	5448 KB	Output is correct
3	Correct	11 ms	5456 KB	Output is correct
4	Correct	10 ms	5332 KB	Output is correct
5	Correct	10 ms	5460 KB	Output is correct
6	Correct	12 ms	5452 KB	Output is correct
7	Correct	291 ms	17016 KB	Output is correct
8	Correct	11 ms	5460 KB	Output is correct
9	Correct	15 ms	5540 KB	Output is correct
10	Correct	16 ms	5444 KB	Output is correct
11	Correct	11 ms	5544 KB	Output is correct
12	Correct	12 ms	5992 KB	Output is correct
13	Correct	12 ms	5920 KB	Output is correct
14	Correct	12 ms	5964 KB	Output is correct
15	Correct	11 ms	5596 KB	Output is correct
16	Correct	10 ms	5592 KB	Output is correct
17	Correct	10 ms	5588 KB	Output is correct
18	Correct	12 ms	5636 KB	Output is correct
19	Correct	13 ms	5704 KB	Output is correct
20	Correct	13 ms	5708 KB	Output is correct
21	Correct	13 ms	5800 KB	Output is correct
22	Correct	11 ms	5804 KB	Output is correct
23	Correct	10 ms	5844 KB	Output is correct
24	Correct	12 ms	5900 KB	Output is correct
25	Correct	12 ms	5972 KB	Output is correct
26	Correct	13 ms	5996 KB	Output is correct
27	Correct	13 ms	5972 KB	Output is correct
28	Correct	13 ms	5972 KB	Output is correct
29	Correct	11 ms	6100 KB	Output is correct
30	Correct	11 ms	6100 KB	Output is correct
31	Correct	14 ms	6096 KB	Output is correct
32	Correct	11 ms	6160 KB	Output is correct
33	Correct	27 ms	10196 KB	Output is correct
34	Correct	40 ms	10160 KB	Output is correct
35	Correct	63 ms	10204 KB	Output is correct
36	Correct	36 ms	10824 KB	Output is correct
37	Correct	32 ms	10916 KB	Output is correct
38	Correct	66 ms	10860 KB	Output is correct
39	Correct	38 ms	11624 KB	Output is correct
40	Correct	46 ms	11624 KB	Output is correct
41	Correct	108 ms	11632 KB	Output is correct
42	Correct	50 ms	12344 KB	Output is correct
43	Correct	42 ms	12372 KB	Output is correct
44	Correct	110 ms	12372 KB	Output is correct
45	Correct	47 ms	13064 KB	Output is correct
46	Correct	60 ms	13068 KB	Output is correct
47	Correct	160 ms	13080 KB	Output is correct
48	Correct	73 ms	13800 KB	Output is correct
49	Correct	58 ms	13768 KB	Output is correct
50	Correct	166 ms	13816 KB	Output is correct
51	Correct	67 ms	14540 KB	Output is correct
52	Correct	72 ms	14676 KB	Output is correct
53	Correct	216 ms	14540 KB	Output is correct
54	Correct	69 ms	15260 KB	Output is correct
55	Correct	69 ms	15168 KB	Output is correct
56	Correct	245 ms	15340 KB	Output is correct
57	Correct	79 ms	15948 KB	Output is correct
58	Correct	81 ms	15956 KB	Output is correct
59	Correct	252 ms	15916 KB	Output is correct
60	Correct	79 ms	16844 KB	Output is correct
61	Correct	77 ms	16680 KB	Output is correct
62	Correct	283 ms	16840 KB	Output is correct
63	Correct	188 ms	16716 KB	Output is correct
64	Correct	301 ms	16764 KB	Output is correct
65	Correct	242 ms	16768 KB	Output is correct
66	Correct	197 ms	16692 KB	Output is correct
67	Correct	186 ms	16768 KB	Output is correct
68	Correct	145 ms	16824 KB	Output is correct
69	Correct	118 ms	16836 KB	Output is correct
70	Correct	114 ms	16720 KB	Output is correct
71	Correct	116 ms	16748 KB	Output is correct
72	Correct	102 ms	16920 KB	Output is correct
73	Correct	125 ms	17392 KB	Output is correct
74	Correct	159 ms	17208 KB	Output is correct
75	Correct	172 ms	17304 KB	Output is correct
76	Correct	162 ms	17356 KB	Output is correct
77	Correct	180 ms	17364 KB	Output is correct
78	Correct	192 ms	17348 KB	Output is correct
79	Correct	157 ms	17356 KB	Output is correct
80	Correct	152 ms	17308 KB	Output is correct
81	Correct	182 ms	17220 KB	Output is correct
82	Correct	148 ms	17208 KB	Output is correct
83	Correct	221 ms	17160 KB	Output is correct
84	Correct	214 ms	17228 KB	Output is correct
85	Correct	189 ms	17220 KB	Output is correct
86	Correct	207 ms	17268 KB	Output is correct
87	Correct	238 ms	17096 KB	Output is correct
88	Correct	217 ms	17228 KB	Output is correct
89	Correct	202 ms	17104 KB	Output is correct
90	Correct	217 ms	17068 KB	Output is correct
91	Correct	221 ms	17104 KB	Output is correct
92	Correct	225 ms	17148 KB	Output is correct