Submission #883250

#	Time	Username	Problem	Language	Result	Execution time	Memory
883250		Servant_of_the_Lord	Mecho (IOI09_mecho)	C++17	100 / 100	595 ms	4008 KiB

mecho

#include <bits/stdc++.h>
#define ll long long

using namespace std;

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll x,y,z,a,b,c;
    cin>>x>>y;
    vector<string>v;
    vector<vector<ll>>w;
    for(ll i=0;i<x;i++)
    {
        string s;
        cin>>s;
        v.push_back(s);
        for(ll j=0;j<x;j++)
        {
            if(v[i][j]=='M')a=i,b=j;
            if(v[i][j]=='H')w.push_back({i,j});
        }
    }
    
    ll l=-1,h=x*x;
    while(l<h)
    {
        ll m=l+(h-l+1)/2;
        vector<string>u;
        for(string i:v)u.push_back(i);
        queue<vector<ll>>q,r;
        for(vector<ll>i:w)q.push(i);
        r.push({a,b});
        q.push({-1,-1});
        r.push({-1,-1});
        bool o=false;
        function<void(ll,ll)>a1=[&](ll a,ll b)
        {
            if(a<0||a>=x||b<0||b>=x||u[a][b]=='H'||u[a][b]=='D'||u[a][b]=='T')return;
            u[a][b]='H';
            q.push({a,b});
        };
        function<void(ll,ll)>a2=[&](ll a,ll b)
        {
            if(a<0||a>=x||b<0||b>=x||u[a][b]=='H'||u[a][b]=='M'||u[a][b]=='T')return;
            if(u[a][b]=='D')o=true;
            u[a][b]='M';
            r.push({a,b});
        };
        for(ll i=0;i<m;i++)
        {
            while(q.front()[0]!=-1)
            {
                a1(q.front()[0]-1,q.front()[1]);
                a1(q.front()[0]+1,q.front()[1]);
                a1(q.front()[0],q.front()[1]-1);
                a1(q.front()[0],q.front()[1]+1);
                q.pop();
            }
            q.pop();
            q.push({-1,-1});
        }
        while(r.front()[0]!=-1)
        {
            
            for(ll i=0;i<y;i++)
            {
                while(r.front()[0]!=-1)
                {
                    if(u[r.front()[0]][r.front()[1]]!='M')
                    {
                        r.pop();
                        continue;
                    }
                    a2(r.front()[0]-1,r.front()[1]);
                    a2(r.front()[0]+1,r.front()[1]);
                    a2(r.front()[0],r.front()[1]-1);
                    a2(r.front()[0],r.front()[1]+1);
                    r.pop();
                }
                r.pop();
                r.push({-1,-1});
            }
            while(q.front()[0]!=-1)
            {
                a1(q.front()[0]-1,q.front()[1]);
                a1(q.front()[0]+1,q.front()[1]);
                a1(q.front()[0],q.front()[1]-1);
                a1(q.front()[0],q.front()[1]+1);
                q.pop();
            }
            q.pop();
            q.push({-1,-1});
        }
        if(o)l=m;
        else h=m-1;
    }
    cout<<l<<'\n';
}

Compilation message (stderr)

mecho.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main()
      | ^~~~
mecho.cpp: In function 'int main()':
mecho.cpp:11:12: warning: unused variable 'z' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c;
      |            ^
mecho.cpp:11:18: warning: unused variable 'c' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c;
      |                  ^
mecho.cpp:35:21: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |         r.push({a,b});
      |                     ^
mecho.cpp:35:21: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100