답안 #554970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554970	2022-04-29T19:11:39 Z	savackexp	Mecho (IOI09_mecho)	C++14	24 / 100	290 ms	17400 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;
            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

24.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	5332 KB	Output is correct
2	Incorrect	12 ms	5332 KB	Output isn't correct
3	Correct	11 ms	5460 KB	Output is correct
4	Incorrect	17 ms	5444 KB	Output isn't correct
5	Incorrect	12 ms	5476 KB	Output isn't correct
6	Incorrect	13 ms	5460 KB	Output isn't correct
7	Incorrect	246 ms	17044 KB	Output isn't correct
8	Incorrect	13 ms	5460 KB	Output isn't correct
9	Incorrect	14 ms	5448 KB	Output isn't correct
10	Incorrect	11 ms	5460 KB	Output isn't correct
11	Incorrect	10 ms	5544 KB	Output isn't correct
12	Incorrect	11 ms	5960 KB	Output isn't correct
13	Correct	12 ms	5920 KB	Output is correct
14	Incorrect	13 ms	6008 KB	Output isn't correct
15	Correct	13 ms	5588 KB	Output is correct
16	Correct	13 ms	5588 KB	Output is correct
17	Correct	13 ms	5632 KB	Output is correct
18	Correct	13 ms	5644 KB	Output is correct
19	Correct	12 ms	5704 KB	Output is correct
20	Correct	10 ms	5704 KB	Output is correct
21	Correct	12 ms	5700 KB	Output is correct
22	Correct	11 ms	5704 KB	Output is correct
23	Correct	11 ms	5900 KB	Output is correct
24	Correct	10 ms	5904 KB	Output is correct
25	Correct	11 ms	5972 KB	Output is correct
26	Correct	11 ms	5956 KB	Output is correct
27	Correct	12 ms	5956 KB	Output is correct
28	Correct	12 ms	5972 KB	Output is correct
29	Correct	13 ms	6092 KB	Output is correct
30	Correct	13 ms	6092 KB	Output is correct
31	Correct	12 ms	6156 KB	Output is correct
32	Correct	13 ms	6156 KB	Output is correct
33	Correct	25 ms	10108 KB	Output is correct
34	Correct	25 ms	10196 KB	Output is correct
35	Incorrect	52 ms	10196 KB	Output isn't correct
36	Correct	34 ms	10928 KB	Output is correct
37	Correct	44 ms	10912 KB	Output is correct
38	Incorrect	83 ms	10916 KB	Output isn't correct
39	Correct	38 ms	11724 KB	Output is correct
40	Correct	34 ms	11604 KB	Output is correct
41	Incorrect	88 ms	11636 KB	Output isn't correct
42	Correct	47 ms	12360 KB	Output is correct
43	Correct	48 ms	12348 KB	Output is correct
44	Incorrect	113 ms	12360 KB	Output isn't correct
45	Correct	49 ms	13012 KB	Output is correct
46	Correct	48 ms	12984 KB	Output is correct
47	Incorrect	125 ms	13044 KB	Output isn't correct
48	Correct	67 ms	13804 KB	Output is correct
49	Correct	65 ms	13804 KB	Output is correct
50	Incorrect	154 ms	13824 KB	Output isn't correct
51	Correct	68 ms	14548 KB	Output is correct
52	Correct	65 ms	14504 KB	Output is correct
53	Incorrect	213 ms	14552 KB	Output isn't correct
54	Correct	69 ms	15260 KB	Output is correct
55	Correct	68 ms	15172 KB	Output is correct
56	Incorrect	209 ms	15272 KB	Output isn't correct
57	Correct	86 ms	16004 KB	Output is correct
58	Correct	75 ms	15948 KB	Output is correct
59	Incorrect	252 ms	16072 KB	Output isn't correct
60	Correct	100 ms	16748 KB	Output is correct
61	Correct	82 ms	16704 KB	Output is correct
62	Incorrect	267 ms	16764 KB	Output isn't correct
63	Incorrect	268 ms	16768 KB	Output isn't correct
64	Correct	272 ms	16844 KB	Output is correct
65	Incorrect	290 ms	16868 KB	Output isn't correct
66	Incorrect	243 ms	16768 KB	Output isn't correct
67	Incorrect	260 ms	16844 KB	Output isn't correct
68	Incorrect	128 ms	16824 KB	Output isn't correct
69	Incorrect	123 ms	16712 KB	Output isn't correct
70	Incorrect	126 ms	16748 KB	Output isn't correct
71	Incorrect	117 ms	16824 KB	Output isn't correct
72	Correct	120 ms	16828 KB	Output is correct
73	Correct	176 ms	17392 KB	Output is correct
74	Correct	184 ms	17400 KB	Output is correct
75	Incorrect	172 ms	17308 KB	Output isn't correct
76	Incorrect	169 ms	17372 KB	Output isn't correct
77	Incorrect	159 ms	17288 KB	Output isn't correct
78	Incorrect	214 ms	17256 KB	Output isn't correct
79	Correct	158 ms	17316 KB	Output is correct
80	Incorrect	153 ms	17320 KB	Output isn't correct
81	Incorrect	161 ms	17312 KB	Output isn't correct
82	Incorrect	174 ms	17332 KB	Output isn't correct
83	Incorrect	205 ms	17164 KB	Output isn't correct
84	Correct	195 ms	17184 KB	Output is correct
85	Incorrect	187 ms	17092 KB	Output isn't correct
86	Incorrect	198 ms	17228 KB	Output isn't correct
87	Incorrect	217 ms	17192 KB	Output isn't correct
88	Incorrect	230 ms	17080 KB	Output isn't correct
89	Correct	196 ms	17168 KB	Output is correct
90	Incorrect	237 ms	17100 KB	Output isn't correct
91	Incorrect	192 ms	17104 KB	Output isn't correct
92	Incorrect	209 ms	17228 KB	Output isn't correct