Submission #886349

#	Time	Username	Problem	Language	Result	Execution time	Memory
886349		Juanchoki	Mecho (IOI09_mecho)	C++14	9 / 100	1056 ms	65536 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct tpos
{
    int i, j, t;
};
bool operator < (const tpos &a, const tpos &b)
{
    if (a.i == b.i) return a.j < b.j;
    return a.i < b.i;
}
char mat[801][801];
char aux[801][801];
int iini, jini;
int n, s; 
vector<tpos> abejas;
bool verifica (int i, int j)
{
    if (i < 0 || j < 0 || i >= n || j >= n)
        return 0;
    return 1;
}
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
void expande_abejas(queue<tpos> &abeja, int t, vector<vector<bool>> &visi)
{
    tpos temp;
    int ti, tj;
    while (!abeja.empty())
    {
        temp = abeja.front(); 
        if (temp.t == t) return;
        abeja.pop();
        visi[temp.i][temp.j] = 1;
        for (int k = 0; k < 4; k++) 
        {
            ti = temp.i + di[k], tj = temp.j + dj[k]; 
            if (!verifica(ti, tj)) continue;
            if (visi[ti][tj])  continue;
            abeja.push({ti, tj, temp.t + 1});
        }
    }
}
bool sepuede(int t)
{
    vector<vector<bool>>visi(n, vector<bool>(n, 0)); //ya lo invadieron las abejas?
    queue<tpos> mecho;
    queue<tpos> abeja;
    mecho.push({iini, jini, 0});
    for (int i = 0, l = abejas.size(); i < l; i++)
        abeja.push({abejas[i].i, abejas[i].j, 0});

    tpos temp;
    int ti, tj;

    while (!abeja.empty())
    {
        temp = abeja.front(); 
        if (temp.t > t) break;
        abeja.pop();
        visi[temp.i][temp.j] = 1;
        for (int k = 0; k < 4; k++) 
        {
            ti = temp.i + di[k], tj = temp.j + dj[k]; 
            if (!verifica(ti, tj)) continue;
            if (visi[ti][tj])  continue;
            abeja.push({ti, tj, temp.t + 1});
        }
    }

    //vector<vector<bool>> yo (n, vector<bool>(n, 0)); //posiciones que ha ocupado el mecho
    bool llego = 0;
    int primero = s;
    while (!mecho.empty())
    {
        temp = mecho.front(); mecho.pop();
        if (visi[temp.i][temp.j]) continue;
        if (temp.t > primero)
        {   
            expande_abejas(abeja, t+(primero)/s, visi);
            primero+= s;
        } 
        if (visi[temp.i][temp.j]) return 0;
        if (mat[temp.i][temp.j] == 'D') return 1;

        for (int k = 0; k < 4; k++) 
        {
            ti = temp.i + di[k], tj = temp.j + dj[k]; 
            if (!verifica(ti, tj)) continue;
            if (visi[ti][tj])  continue;
            mecho.push({ti, tj, temp.t + 1});
        }
    }
    return 0;
}
int main ()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            {
                cin >> mat[i][j];
                aux[i][j] = mat[i][j];
                if (mat[i][j] == 'M')   
                    {
                        iini = i;
                        jini = j;
                        continue;
                    }
                if (mat[i][j] == 'H')
                    abejas.pb({i, j, 0});
            }

    int l = 0, r = (1<<11), resp;

    while (l <= r)
    {
        int mit = (l+r)>>1;
        if (sepuede(mit))
        {
            resp = mit;
            l = mit+1;
            continue;
        }
        r = mit-1;
    }
    cout << resp;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool sepuede(int)':
mecho.cpp:72:10: warning: unused variable 'llego' [-Wunused-variable]
   72 |     bool llego = 0;
      |          ^~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:127:13: warning: 'resp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     cout << resp;
      |             ^~~~

• Subtask 1: 9 / 100