답안 #554937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554937	2022-04-29T16:31:19 Z	savackexp	Mecho (IOI09_mecho)	C++14	24 / 100	283 ms	16760 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])/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

#	결과	실행 시간	메모리	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