답안 #554991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554991	2022-04-29T19:35:56 Z	savackexp	Mecho (IOI09_mecho)	C++14	22 / 100	300 ms	16844 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;
        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

22.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	5460 KB	Output is correct
2	Correct	15 ms	5332 KB	Output is correct
3	Correct	10 ms	5452 KB	Output is correct
4	Correct	10 ms	5456 KB	Output is correct
5	Incorrect	11 ms	5460 KB	Output isn't correct
6	Incorrect	12 ms	5492 KB	Output isn't correct
7	Incorrect	235 ms	16460 KB	Output isn't correct
8	Correct	10 ms	5460 KB	Output is correct
9	Incorrect	13 ms	5544 KB	Output isn't correct
10	Incorrect	10 ms	5548 KB	Output isn't correct
11	Incorrect	11 ms	5540 KB	Output isn't correct
12	Incorrect	11 ms	5992 KB	Output isn't correct
13	Correct	11 ms	5920 KB	Output is correct
14	Correct	11 ms	5972 KB	Output is correct
15	Correct	11 ms	5588 KB	Output is correct
16	Incorrect	12 ms	5588 KB	Output isn't correct
17	Correct	11 ms	5588 KB	Output is correct
18	Incorrect	12 ms	5588 KB	Output isn't correct
19	Correct	11 ms	5588 KB	Output is correct
20	Incorrect	14 ms	5704 KB	Output isn't correct
21	Correct	12 ms	5716 KB	Output is correct
22	Incorrect	11 ms	5796 KB	Output isn't correct
23	Correct	10 ms	5844 KB	Output is correct
24	Incorrect	11 ms	5844 KB	Output isn't correct
25	Correct	10 ms	5972 KB	Output is correct
26	Incorrect	12 ms	5992 KB	Output isn't correct
27	Correct	13 ms	6044 KB	Output is correct
28	Incorrect	12 ms	5972 KB	Output isn't correct
29	Correct	15 ms	6104 KB	Output is correct
30	Incorrect	13 ms	6104 KB	Output isn't correct
31	Correct	15 ms	6156 KB	Output is correct
32	Incorrect	18 ms	6148 KB	Output isn't correct
33	Correct	37 ms	10068 KB	Output is correct
34	Incorrect	29 ms	10068 KB	Output isn't correct
35	Incorrect	53 ms	10068 KB	Output isn't correct
36	Correct	33 ms	10752 KB	Output is correct
37	Incorrect	33 ms	10708 KB	Output isn't correct
38	Incorrect	72 ms	10708 KB	Output isn't correct
39	Correct	39 ms	11424 KB	Output is correct
40	Incorrect	51 ms	11428 KB	Output isn't correct
41	Incorrect	103 ms	11436 KB	Output isn't correct
42	Correct	48 ms	11988 KB	Output is correct
43	Incorrect	41 ms	11988 KB	Output isn't correct
44	Incorrect	111 ms	12104 KB	Output isn't correct
45	Correct	50 ms	12876 KB	Output is correct
46	Incorrect	52 ms	12772 KB	Output isn't correct
47	Incorrect	136 ms	12784 KB	Output isn't correct
48	Correct	63 ms	13524 KB	Output is correct
49	Incorrect	65 ms	13452 KB	Output isn't correct
50	Incorrect	187 ms	13460 KB	Output isn't correct
51	Correct	63 ms	14116 KB	Output is correct
52	Incorrect	64 ms	14036 KB	Output isn't correct
53	Incorrect	192 ms	14144 KB	Output isn't correct
54	Correct	79 ms	14816 KB	Output is correct
55	Incorrect	79 ms	14796 KB	Output isn't correct
56	Incorrect	216 ms	14792 KB	Output isn't correct
57	Correct	76 ms	15428 KB	Output is correct
58	Incorrect	82 ms	15452 KB	Output isn't correct
59	Incorrect	260 ms	15472 KB	Output isn't correct
60	Correct	84 ms	16120 KB	Output is correct
61	Incorrect	81 ms	16108 KB	Output isn't correct
62	Incorrect	300 ms	16136 KB	Output isn't correct
63	Incorrect	182 ms	16140 KB	Output isn't correct
64	Incorrect	296 ms	16144 KB	Output isn't correct
65	Incorrect	261 ms	16204 KB	Output isn't correct
66	Correct	202 ms	16204 KB	Output is correct
67	Correct	187 ms	16140 KB	Output is correct
68	Incorrect	114 ms	16256 KB	Output isn't correct
69	Incorrect	114 ms	16128 KB	Output isn't correct
70	Incorrect	97 ms	16200 KB	Output isn't correct
71	Incorrect	108 ms	16140 KB	Output isn't correct
72	Correct	106 ms	16200 KB	Output is correct
73	Correct	125 ms	16844 KB	Output is correct
74	Incorrect	156 ms	16648 KB	Output isn't correct
75	Incorrect	189 ms	16796 KB	Output isn't correct
76	Incorrect	149 ms	16716 KB	Output isn't correct
77	Incorrect	167 ms	16728 KB	Output isn't correct
78	Correct	194 ms	16600 KB	Output is correct
79	Incorrect	148 ms	16588 KB	Output isn't correct
80	Incorrect	158 ms	16688 KB	Output isn't correct
81	Incorrect	185 ms	16680 KB	Output isn't correct
82	Incorrect	155 ms	16668 KB	Output isn't correct
83	Incorrect	189 ms	16524 KB	Output isn't correct
84	Incorrect	202 ms	16600 KB	Output isn't correct
85	Incorrect	206 ms	16540 KB	Output isn't correct
86	Incorrect	201 ms	16592 KB	Output isn't correct
87	Incorrect	211 ms	16516 KB	Output isn't correct
88	Incorrect	188 ms	16472 KB	Output isn't correct
89	Incorrect	231 ms	16580 KB	Output isn't correct
90	Incorrect	234 ms	16476 KB	Output isn't correct
91	Incorrect	210 ms	16400 KB	Output isn't correct
92	Incorrect	229 ms	16388 KB	Output isn't correct