oj.uz

답안 #886355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886355 2023-12-11T23:53:34 Z Juanchoki Mecho (IOI09_mecho) C++14
4 / 100
 237 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 << 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: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
4.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 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 Correct 1 ms 348 KB Output is correct
7 Runtime error 160 ms 65536 KB Execution killed with signal 9
8 Incorrect 0 ms 348 KB Output isn't 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 9 ms 1116 KB Output isn't correct
14 Incorrect 120 ms 17252 KB Output isn't correct
15 Incorrect 0 ms 344 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 344 KB Output isn't correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Incorrect 0 ms 604 KB Output isn't correct
22 Incorrect 0 ms 604 KB Output isn't correct
23 Incorrect 0 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 2652 KB Output isn't correct
31 Incorrect 1 ms 2652 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 2908 KB Output isn't correct
35 Runtime error 109 ms 65536 KB Execution killed with signal 9
36 Incorrect 8 ms 2904 KB Output isn't correct
37 Incorrect 8 ms 2908 KB Output isn't correct
38 Runtime error 128 ms 65536 KB Execution killed with signal 9
39 Incorrect 12 ms 2908 KB Output isn't correct
40 Incorrect 9 ms 2908 KB Output isn't correct
41 Runtime error 132 ms 65536 KB Execution killed with signal 9
42 Incorrect 11 ms 3052 KB Output isn't correct
43 Incorrect 11 ms 2908 KB Output isn't correct
44 Runtime error 109 ms 65536 KB Execution killed with signal 9
45 Incorrect 14 ms 3164 KB Output isn't correct
46 Incorrect 13 ms 3416 KB Output isn't correct
47 Runtime error 134 ms 65536 KB Execution killed with signal 9
48 Incorrect 16 ms 3164 KB Output isn't correct
49 Incorrect 16 ms 3164 KB Output isn't correct
50 Runtime error 116 ms 65536 KB Execution killed with signal 9
51 Incorrect 18 ms 3160 KB Output isn't correct
52 Incorrect 18 ms 3164 KB Output isn't correct
53 Runtime error 139 ms 65536 KB Execution killed with signal 9
54 Incorrect 21 ms 3164 KB Output isn't correct
55 Incorrect 27 ms 3204 KB Output isn't correct
56 Runtime error 140 ms 65536 KB Execution killed with signal 9
57 Incorrect 24 ms 3456 KB Output isn't correct
58 Incorrect 30 ms 3412 KB Output isn't correct
59 Runtime error 146 ms 65536 KB Execution killed with signal 9
60 Incorrect 27 ms 3672 KB Output isn't correct
61 Incorrect 27 ms 3664 KB Output isn't correct
62 Runtime error 144 ms 65536 KB Execution killed with signal 9
63 Incorrect 107 ms 3644 KB Output isn't correct
64 Incorrect 150 ms 3640 KB Output isn't correct
65 Incorrect 128 ms 3696 KB Output isn't correct
66 Incorrect 112 ms 3680 KB Output isn't correct
67 Incorrect 129 ms 3664 KB Output isn't correct
68 Incorrect 52 ms 3664 KB Output isn't correct
69 Incorrect 49 ms 3672 KB Output isn't correct
70 Incorrect 39 ms 3668 KB Output isn't correct
71 Incorrect 41 ms 3688 KB Output isn't correct
72 Incorrect 41 ms 3540 KB Output isn't correct
73 Runtime error 221 ms 65536 KB Execution killed with signal 9
74 Runtime error 226 ms 65536 KB Execution killed with signal 9
75 Runtime error 194 ms 65536 KB Execution killed with signal 9
76 Runtime error 237 ms 65536 KB Execution killed with signal 9
77 Runtime error 222 ms 65536 KB Execution killed with signal 9
78 Runtime error 195 ms 65536 KB Execution killed with signal 9
79 Runtime error 199 ms 65536 KB Execution killed with signal 9
80 Runtime error 198 ms 65536 KB Execution killed with signal 9
81 Runtime error 172 ms 65536 KB Execution killed with signal 9
82 Runtime error 186 ms 65536 KB Execution killed with signal 9
83 Runtime error 180 ms 65536 KB Execution killed with signal 9
84 Runtime error 181 ms 65536 KB Execution killed with signal 9
85 Runtime error 182 ms 65536 KB Execution killed with signal 9
86 Runtime error 182 ms 65536 KB Execution killed with signal 9
87 Runtime error 178 ms 65536 KB Execution killed with signal 9
88 Runtime error 142 ms 65536 KB Execution killed with signal 9
89 Runtime error 140 ms 65536 KB Execution killed with signal 9
90 Runtime error 164 ms 65536 KB Execution killed with signal 9
91 Runtime error 174 ms 65536 KB Execution killed with signal 9
92 Runtime error 167 ms 65536 KB Execution killed with signal 9