oj.uz

Submission #886356

# Submission time Handle Problem Language Result Execution time Memory
886356 2023-12-11T23:54:19 Z Juanchoki Mecho (IOI09_mecho) C++14
4 / 100
 223 ms 65536 KB 
#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});

    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 = -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 << -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;
}

Compilation message

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;
      |         ^~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:108:29: warning: variable 'resp' set but not used [-Wunused-but-set-variable]
  108 |     int l = 0, r = (1<<11), resp = -1;
      |                             ^~~~

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Runtime error 154 ms 65536 KB Execution killed with signal 9
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 1 ms 2652 KB Output isn't correct
13 Incorrect 11 ms 1112 KB Output isn't correct
14 Correct 133 ms 17192 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Incorrect 1 ms 604 KB Output isn't correct
24 Incorrect 0 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 2652 KB Output isn't correct
31 Incorrect 1 ms 2648 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 126 ms 65536 KB Execution killed with signal 9
36 Incorrect 7 ms 2908 KB Output isn't correct
37 Incorrect 7 ms 2908 KB Output isn't correct
38 Runtime error 129 ms 65536 KB Execution killed with signal 9
39 Incorrect 9 ms 2904 KB Output isn't correct
40 Incorrect 9 ms 2984 KB Output isn't correct
41 Runtime error 110 ms 65536 KB Execution killed with signal 9
42 Incorrect 11 ms 3060 KB Output isn't correct
43 Incorrect 11 ms 2976 KB Output isn't correct
44 Runtime error 133 ms 65536 KB Execution killed with signal 9
45 Incorrect 13 ms 3068 KB Output isn't correct
46 Incorrect 13 ms 3164 KB Output isn't correct
47 Runtime error 135 ms 65536 KB Execution killed with signal 9
48 Incorrect 15 ms 3164 KB Output isn't correct
49 Incorrect 15 ms 3164 KB Output isn't correct
50 Runtime error 113 ms 65536 KB Execution killed with signal 9
51 Incorrect 17 ms 3164 KB Output isn't correct
52 Incorrect 17 ms 3160 KB Output isn't correct
53 Runtime error 138 ms 65536 KB Execution killed with signal 9
54 Incorrect 21 ms 3164 KB Output isn't correct
55 Incorrect 20 ms 3160 KB Output isn't correct
56 Runtime error 140 ms 65536 KB Execution killed with signal 9
57 Incorrect 24 ms 3412 KB Output isn't correct
58 Incorrect 23 ms 3368 KB Output isn't correct
59 Runtime error 144 ms 65536 KB Execution killed with signal 9
60 Incorrect 26 ms 3676 KB Output isn't correct
61 Incorrect 26 ms 3676 KB Output isn't correct
62 Runtime error 120 ms 65536 KB Execution killed with signal 9
63 Incorrect 110 ms 3668 KB Output isn't correct
64 Incorrect 157 ms 3680 KB Output isn't correct
65 Incorrect 123 ms 3660 KB Output isn't correct
66 Incorrect 123 ms 3680 KB Output isn't correct
67 Correct 129 ms 3664 KB Output is correct
68 Incorrect 53 ms 3692 KB Output isn't correct
69 Incorrect 49 ms 3624 KB Output isn't correct
70 Incorrect 39 ms 3564 KB Output isn't correct
71 Incorrect 43 ms 3672 KB Output isn't correct
72 Incorrect 37 ms 3620 KB Output isn't correct
73 Runtime error 223 ms 65536 KB Execution killed with signal 9
74 Runtime error 223 ms 65536 KB Execution killed with signal 9
75 Runtime error 195 ms 65536 KB Execution killed with signal 9
76 Runtime error 223 ms 65536 KB Execution killed with signal 9
77 Runtime error 219 ms 65536 KB Execution killed with signal 9
78 Runtime error 175 ms 65536 KB Execution killed with signal 9
79 Runtime error 198 ms 65536 KB Execution killed with signal 9
80 Runtime error 173 ms 65536 KB Execution killed with signal 9
81 Runtime error 194 ms 65536 KB Execution killed with signal 9
82 Runtime error 202 ms 65536 KB Execution killed with signal 9
83 Runtime error 178 ms 65536 KB Execution killed with signal 9
84 Runtime error 199 ms 65536 KB Execution killed with signal 9
85 Runtime error 180 ms 65536 KB Execution killed with signal 9
86 Runtime error 183 ms 65536 KB Execution killed with signal 9
87 Runtime error 177 ms 65536 KB Execution killed with signal 9
88 Runtime error 165 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 145 ms 65536 KB Execution killed with signal 9