Submission #593256

#	Time	Username	Problem	Language	Result	Execution time	Memory
593256		Bench0310	Mecho (IOI09_mecho)	C++17	100 / 100	374 ms	7184 KiB

mecho

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,one;
    cin >> n >> one;
    vector<string> s(n);
    array<int,2> bear;
    array<int,2> house;
    vector<array<int,2>> bees;
    for(int i=0;i<n;i++)
    {
        cin >> s[i];
        for(int j=0;j<n;j++)
        {
            if(s[i][j]=='M') bear={i,j};
            if(s[i][j]=='D') house={i,j};
            if(s[i][j]=='H') bees.push_back({i,j});
        }
    }
    auto in=[&](int r,int c)->bool{return (0<=r&&r<n&&0<=c&&c<n);};
    vector<array<int,2>> z={{1,0},{-1,0},{0,-1},{0,1}};
    int ltime=-1,rtime=n*n;
    while(ltime<rtime-1)
    {
        int m=(ltime+rtime)/2;
        queue<array<int,2>> qbees,qbear;
        vector dbee(n,vector(n,int(-1)));
        auto add_bee=[&](int r,int c,int nd)
        {
            if(in(r,c)&&s[r][c]!='T'&&s[r][c]!='D'&&dbee[r][c]==-1)
            {
                qbees.push({r,c});
                dbee[r][c]=nd;
            }
        };
        vector dbear(n,vector(n,int(-1)));
        auto add_bear=[&](int r,int c,int nd)
        {
            if(in(r,c)&&s[r][c]!='T'&&dbee[r][c]==-1&&dbear[r][c]==-1)
            {
                qbear.push({r,c});
                dbear[r][c]=nd;
            }
        };
        for(auto [r,c]:bees) add_bee(r,c,0);
        add_bear(bear[0],bear[1],0);
        for(int i=0;!qbear.empty();i++)
        {
            while(!qbear.empty())
            {
                auto [r,c]=qbear.front();
                int d=dbear[r][c];
                if(d<(i-m+1)*one)
                {
                    qbear.pop();
                    if(dbee[r][c]!=-1) continue;
                    for(auto [dr,dc]:z) add_bear(r+dr,c+dc,dbear[r][c]+1);
                }
                else break;
            }
            while(!qbees.empty())
            {
                auto [r,c]=qbees.front();
                int d=dbee[r][c];
                if(d<=i)
                {
                    qbees.pop();
                    for(auto [dr,dc]:z) add_bee(r+dr,c+dc,dbee[r][c]+1);
                }
                else break;
            }
        }
        if(dbear[house[0]][house[1]]!=-1) ltime=m;
        else rtime=m;
    }
    cout << ltime << "\n";
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:79:36: warning: 'house.std::array<int, 2>::_M_elems[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         if(dbear[house[0]][house[1]]!=-1) ltime=m;
      |                                    ^
mecho.cpp:13:18: warning: 'bear.std::array<int, 2>::_M_elems[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 |     array<int,2> bear;
      |                  ^~~~
mecho.cpp:79:26: warning: 'house.std::array<int, 2>::_M_elems[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         if(dbear[house[0]][house[1]]!=-1) ltime=m;
      |                          ^
mecho.cpp:13:18: warning: 'bear.std::array<int, 2>::_M_elems[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 |     array<int,2> bear;
      |                  ^~~~

• Subtask 1: 100 / 100