제출 #886353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886353		Juanchoki	Mecho (IOI09_mecho)	C++14	22 / 100	225 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];
int tiempo[801][801];
//int tiempo_oso[801][801];
int iini, jini, ifin, jfin;
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)
{
    tpos t;
    int ti, tj;
    while (!abeja.empty())
    {
        t = abeja.front(); abeja.pop();
        tiempo[t.i][t.j] = t.t;
        for (int k = 0; k < 4; k++) 
        {
            ti = t.i + di[k], tj = t.j + dj[k]; 
            if (!verifica(ti, tj)) continue;
            if (tiempo[ti][tj] != -1)  continue;
            if (mat[ti][tj] == 'T') continue;
            abeja.push({ti, tj, t.t + 1});
        }
    }
}
bool sepuede(int t)
{
    vector<vector<bool>>visi(n, vector<bool>(n, 0)); //llegue?
    queue<tpos> mecho;
    mecho.push({iini, jini, t+1});

    tpos temp;
    int ti, tj;
   // cout << t << '\n';
    int turno = 0;
    visi[iini][jini] = 1;
    while (!mecho.empty())
    {
        temp = mecho.front(); mecho.pop();
		//cout << temp.i << " " << temp.j << " " <<temp.t << '\n';
      /*  if (t + (temp.t - t)/(s+1) > tiempo[temp.i][temp.j]) continue;
        tiempo_oso[temp.i][temp.j] = temp.t;*/
        int realt = (temp.t - t)/(1+s);
        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;
            if (mat[ti][tj] == 'T') continue;
            if (tiempo[ti][tj] < (t + (temp.t - t + 1)/(1+s))) continue;
            mecho.push({ti, tj, temp.t + 1});
            visi[ti][tj] = 1;
        }
    }
    
    return 0;
}

int main ()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            {
                tiempo[i][j] = -1;
                cin >> mat[i][j];
                if (mat[i][j] == 'M')   
                    {
                        iini = i;
                        jini = j;
                        continue;
                    }
                if (mat[i][j] == 'H')
                {
                    abejas.pb({i, j, 0});
                    tiempo[i][j] = 0;
                }
                if (mat[i][j] == 'D')
                {
                    ifin = i;
                    jfin = j;
                }    
            }
    queue<tpos> a;
    for (int i = 0, l = abejas.size(); i < l; i++)
        a.push(abejas[i]);
    int l = 0, r = (1<<11), resp = 0;
    expande_abejas(a);
    while (l <= r)
    {
        int mit = (l+r)>>1;
        if (sepuede(mit))
        {
            resp = mit;
            l = mit+1;
            continue;
        }
        r = mit-1;
    }
    
    cout << resp-1;
   /* for (int i = 0; i < n; i++, cout << '\n')
        for (int j = 0; j < n; j++)
            cout << tiempo[i][j] << " ";
    cout << '\n';
    sepuede(2);
    for (int i = 0; i < n; i++, cout << '\n')
        for (int j = 0; j < n; j++)
            cout << tiempo_oso[i][j] << " ";
    //cout << resp; 
	//sepuede(1);
    */
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'bool sepuede(int)':
mecho.cpp:62:13: warning: unused variable 'realt' [-Wunused-variable]
   62 |         int realt = (temp.t - t)/(1+s);
      |             ^~~~~
mecho.cpp:54:9: warning: unused variable 'turno' [-Wunused-variable]
   54 |     int turno = 0;
      |         ^~~~~

• Subtask 1: 22 / 100