Submission #554973

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
554973	2022-04-29T19:17:24 Z	savackexp	Mecho (IOI09_mecho)	C++14	19 / 100	557 ms	16772 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';
}
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] + u)/k;
                if(levelh[nx][ny] <= 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:125: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]
  125 |     for(int i=0;i<h.size();i++)
      |                 ~^~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:167:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |             for(int j=0;j<s.size();j++)
      |                         ~^~~~~~~~~

Subtask #1

19.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	5332 KB	Output is correct
2	Correct	13 ms	5452 KB	Output is correct
3	Correct	14 ms	5444 KB	Output is correct
4	Correct	12 ms	5332 KB	Output is correct
5	Incorrect	17 ms	5460 KB	Output isn't correct
6	Incorrect	13 ms	5460 KB	Output isn't correct
7	Incorrect	300 ms	16288 KB	Output isn't correct
8	Correct	10 ms	5460 KB	Output is correct
9	Incorrect	11 ms	5460 KB	Output isn't correct
10	Incorrect	11 ms	5536 KB	Output isn't correct
11	Incorrect	12 ms	5460 KB	Output isn't correct
12	Incorrect	18 ms	5988 KB	Output isn't correct
13	Incorrect	13 ms	5916 KB	Output isn't correct
14	Correct	14 ms	5972 KB	Output is correct
15	Correct	17 ms	5592 KB	Output is correct
16	Incorrect	11 ms	5588 KB	Output isn't correct
17	Correct	11 ms	5588 KB	Output is correct
18	Incorrect	10 ms	5636 KB	Output isn't correct
19	Correct	11 ms	5700 KB	Output is correct
20	Incorrect	11 ms	5588 KB	Output isn't correct
21	Correct	10 ms	5804 KB	Output is correct
22	Incorrect	11 ms	5716 KB	Output isn't correct
23	Correct	13 ms	5900 KB	Output is correct
24	Incorrect	12 ms	5900 KB	Output isn't correct
25	Correct	13 ms	5972 KB	Output is correct
26	Incorrect	18 ms	5988 KB	Output isn't correct
27	Correct	12 ms	5924 KB	Output is correct
28	Incorrect	11 ms	6100 KB	Output isn't correct
29	Correct	10 ms	6100 KB	Output is correct
30	Incorrect	11 ms	5972 KB	Output isn't correct
31	Correct	12 ms	6100 KB	Output is correct
32	Incorrect	14 ms	6160 KB	Output isn't correct
33	Correct	31 ms	10068 KB	Output is correct
34	Incorrect	33 ms	10192 KB	Output isn't correct
35	Incorrect	92 ms	10084 KB	Output isn't correct
36	Correct	37 ms	10764 KB	Output is correct
37	Incorrect	37 ms	10752 KB	Output isn't correct
38	Incorrect	119 ms	10772 KB	Output isn't correct
39	Correct	45 ms	11432 KB	Output is correct
40	Incorrect	45 ms	11428 KB	Output isn't correct
41	Incorrect	156 ms	11348 KB	Output isn't correct
42	Correct	50 ms	12096 KB	Output is correct
43	Incorrect	50 ms	11992 KB	Output isn't correct
44	Incorrect	181 ms	12108 KB	Output isn't correct
45	Correct	60 ms	12728 KB	Output is correct
46	Incorrect	56 ms	12772 KB	Output isn't correct
47	Incorrect	257 ms	12788 KB	Output isn't correct
48	Correct	57 ms	13444 KB	Output is correct
49	Incorrect	57 ms	13448 KB	Output isn't correct
50	Incorrect	312 ms	13372 KB	Output isn't correct
51	Correct	72 ms	14036 KB	Output is correct
52	Incorrect	63 ms	14116 KB	Output isn't correct
53	Incorrect	321 ms	14184 KB	Output isn't correct
54	Correct	77 ms	14780 KB	Output is correct
55	Incorrect	82 ms	14792 KB	Output isn't correct
56	Incorrect	387 ms	14920 KB	Output isn't correct
57	Correct	77 ms	15464 KB	Output is correct
58	Incorrect	93 ms	15456 KB	Output isn't correct
59	Incorrect	456 ms	15472 KB	Output isn't correct
60	Correct	87 ms	16120 KB	Output is correct
61	Incorrect	108 ms	16124 KB	Output isn't correct
62	Incorrect	557 ms	16060 KB	Output isn't correct
63	Correct	220 ms	16140 KB	Output is correct
64	Incorrect	400 ms	16040 KB	Output isn't correct
65	Incorrect	334 ms	16144 KB	Output isn't correct
66	Incorrect	233 ms	16140 KB	Output isn't correct
67	Correct	213 ms	16148 KB	Output is correct
68	Incorrect	147 ms	16252 KB	Output isn't correct
69	Incorrect	161 ms	16140 KB	Output isn't correct
70	Incorrect	106 ms	16284 KB	Output isn't correct
71	Incorrect	118 ms	16076 KB	Output isn't correct
72	Incorrect	119 ms	16196 KB	Output isn't correct
73	Incorrect	187 ms	16768 KB	Output isn't correct
74	Incorrect	210 ms	16772 KB	Output isn't correct
75	Incorrect	213 ms	16748 KB	Output isn't correct
76	Incorrect	206 ms	16696 KB	Output isn't correct
77	Incorrect	197 ms	16684 KB	Output isn't correct
78	Correct	254 ms	16748 KB	Output is correct
79	Incorrect	205 ms	16684 KB	Output isn't correct
80	Incorrect	172 ms	16596 KB	Output isn't correct
81	Incorrect	200 ms	16696 KB	Output isn't correct
82	Incorrect	213 ms	16688 KB	Output isn't correct
83	Incorrect	238 ms	16528 KB	Output isn't correct
84	Incorrect	299 ms	16512 KB	Output isn't correct
85	Incorrect	324 ms	16568 KB	Output isn't correct
86	Incorrect	262 ms	16604 KB	Output isn't correct
87	Incorrect	267 ms	16588 KB	Output isn't correct
88	Incorrect	318 ms	16460 KB	Output isn't correct
89	Incorrect	367 ms	16400 KB	Output isn't correct
90	Incorrect	326 ms	16608 KB	Output isn't correct
91	Incorrect	326 ms	16484 KB	Output isn't correct
92	Incorrect	384 ms	16484 KB	Output isn't correct