Submission #886360

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886360	2023-12-12T00:08:56 Z	Juanchoki	Mecho (IOI09_mecho)	C++14	4 / 100	227 ms	65536 KB

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[850][850];
int tiempo[850][850];
//int tiempo_oso[850][850];
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;
            if (mat[ti][tj] == 'M') 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, 0});

    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;*/
        
        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/s ) continue;
            mecho.push({ti, tj, temp.t + 1});
            visi[ti][tj] = 1;
        }
    }
    if (visi[ifin][jfin]) return 1;
    for (int k = 0; k < 4; k++) 
    {
        ti = ifin + di[k], tj = jfin + dj[k];
        if (visi[ti][tj]) return 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<<10), resp = -1;
    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;
   /* 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;
}

Compilation message

mecho.cpp: In function 'bool sepuede(int)':
mecho.cpp:55:9: warning: unused variable 'turno' [-Wunused-variable]
   55 |     int turno = 0;
      |         ^~~~~

Subtask #1

4.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	348 KB	Execution killed with signal 11
2	Runtime error	1 ms	604 KB	Execution killed with signal 11
3	Runtime error	1 ms	604 KB	Execution killed with signal 11
4	Runtime error	1 ms	604 KB	Execution killed with signal 11
5	Incorrect	0 ms	348 KB	Output isn't correct
6	Runtime error	1 ms	604 KB	Execution killed with signal 11
7	Runtime error	154 ms	65536 KB	Execution killed with signal 9
8	Runtime error	1 ms	604 KB	Execution killed with signal 11
9	Runtime error	1 ms	604 KB	Execution killed with signal 11
10	Runtime error	1 ms	604 KB	Execution killed with signal 11
11	Runtime error	1 ms	604 KB	Execution killed with signal 11
12	Incorrect	1 ms	2652 KB	Output isn't correct
13	Incorrect	12 ms	1340 KB	Output isn't correct
14	Correct	135 ms	17300 KB	Output is correct
15	Runtime error	1 ms	600 KB	Execution killed with signal 7
16	Incorrect	0 ms	348 KB	Output isn't correct
17	Runtime error	1 ms	604 KB	Execution killed with signal 7
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Runtime error	1 ms	604 KB	Execution killed with signal 7
20	Incorrect	0 ms	348 KB	Output isn't correct
21	Runtime error	1 ms	860 KB	Execution killed with signal 7
22	Incorrect	0 ms	604 KB	Output isn't correct
23	Incorrect	1 ms	604 KB	Output isn't correct
24	Incorrect	1 ms	604 KB	Output isn't correct
25	Incorrect	1 ms	2652 KB	Output isn't correct
26	Incorrect	1 ms	2652 KB	Output isn't correct
27	Incorrect	1 ms	2652 KB	Output isn't correct
28	Incorrect	1 ms	2652 KB	Output isn't correct
29	Incorrect	1 ms	2652 KB	Output isn't correct
30	Incorrect	1 ms	2648 KB	Output isn't correct
31	Incorrect	1 ms	2904 KB	Output isn't correct
32	Incorrect	1 ms	2652 KB	Output isn't correct
33	Incorrect	6 ms	2908 KB	Output isn't correct
34	Incorrect	6 ms	2904 KB	Output isn't correct
35	Runtime error	129 ms	65536 KB	Execution killed with signal 9
36	Incorrect	7 ms	2908 KB	Output isn't correct
37	Incorrect	7 ms	3000 KB	Output isn't correct
38	Runtime error	114 ms	65536 KB	Execution killed with signal 9
39	Incorrect	9 ms	2908 KB	Output isn't correct
40	Incorrect	9 ms	2908 KB	Output isn't correct
41	Runtime error	128 ms	65536 KB	Execution killed with signal 9
42	Incorrect	10 ms	2904 KB	Output isn't correct
43	Incorrect	11 ms	3084 KB	Output isn't correct
44	Runtime error	136 ms	65536 KB	Execution killed with signal 9
45	Incorrect	13 ms	3192 KB	Output isn't correct
46	Incorrect	13 ms	3164 KB	Output isn't correct
47	Runtime error	137 ms	65536 KB	Execution killed with signal 9
48	Incorrect	19 ms	3160 KB	Output isn't correct
49	Incorrect	15 ms	3164 KB	Output isn't correct
50	Runtime error	112 ms	65536 KB	Execution killed with signal 9
51	Incorrect	21 ms	3164 KB	Output isn't correct
52	Incorrect	18 ms	3164 KB	Output isn't correct
53	Runtime error	138 ms	65536 KB	Execution killed with signal 9
54	Incorrect	20 ms	3352 KB	Output isn't correct
55	Incorrect	20 ms	3416 KB	Output isn't correct
56	Runtime error	143 ms	65536 KB	Execution killed with signal 9
57	Incorrect	22 ms	3552 KB	Output isn't correct
58	Incorrect	23 ms	3672 KB	Output isn't correct
59	Runtime error	140 ms	65536 KB	Execution killed with signal 9
60	Incorrect	27 ms	3676 KB	Output isn't correct
61	Incorrect	26 ms	3768 KB	Output isn't correct
62	Runtime error	121 ms	65536 KB	Execution killed with signal 9
63	Runtime error	37 ms	7512 KB	Execution killed with signal 11
64	Runtime error	72 ms	7464 KB	Execution killed with signal 11
65	Runtime error	43 ms	7380 KB	Execution killed with signal 11
66	Runtime error	40 ms	7472 KB	Execution killed with signal 11
67	Runtime error	40 ms	7372 KB	Execution killed with signal 11
68	Runtime error	38 ms	7508 KB	Execution killed with signal 11
69	Runtime error	37 ms	7516 KB	Execution killed with signal 11
70	Runtime error	38 ms	7512 KB	Execution killed with signal 11
71	Runtime error	38 ms	7504 KB	Execution killed with signal 11
72	Runtime error	38 ms	7508 KB	Execution killed with signal 11
73	Runtime error	222 ms	65536 KB	Execution killed with signal 9
74	Runtime error	221 ms	65536 KB	Execution killed with signal 9
75	Runtime error	227 ms	65536 KB	Execution killed with signal 9
76	Runtime error	195 ms	65536 KB	Execution killed with signal 9
77	Runtime error	223 ms	65536 KB	Execution killed with signal 9
78	Runtime error	192 ms	65536 KB	Execution killed with signal 9
79	Runtime error	181 ms	65536 KB	Execution killed with signal 9
80	Runtime error	176 ms	65536 KB	Execution killed with signal 9
81	Runtime error	172 ms	65536 KB	Execution killed with signal 9
82	Runtime error	199 ms	65536 KB	Execution killed with signal 9
83	Runtime error	180 ms	65536 KB	Execution killed with signal 9
84	Runtime error	178 ms	65536 KB	Execution killed with signal 9
85	Runtime error	180 ms	65536 KB	Execution killed with signal 9
86	Runtime error	184 ms	65536 KB	Execution killed with signal 9
87	Runtime error	174 ms	65536 KB	Execution killed with signal 9
88	Runtime error	164 ms	65536 KB	Execution killed with signal 9
89	Runtime error	163 ms	65536 KB	Execution killed with signal 9
90	Runtime error	167 ms	65536 KB	Execution killed with signal 9
91	Runtime error	166 ms	65536 KB	Execution killed with signal 9
92	Runtime error	163 ms	65536 KB	Execution killed with signal 9