oj.uz

답안 #886353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886353 2023-12-11T23:50:14 Z Juanchoki Mecho (IOI09_mecho) C++14
22 / 100
 225 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+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;
}

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
22.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Runtime error 156 ms 65536 KB Execution killed with signal 9
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 2648 KB Output isn't correct
13 Incorrect 10 ms 1320 KB Output isn't correct
14 Incorrect 146 ms 17636 KB Output isn't correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Incorrect 1 ms 2652 KB Output isn't correct
30 Correct 1 ms 2648 KB Output is correct
31 Incorrect 1 ms 2648 KB Output isn't correct
32 Correct 1 ms 2652 KB Output is correct
33 Incorrect 6 ms 2916 KB Output isn't correct
34 Incorrect 6 ms 2908 KB Output isn't correct
35 Runtime error 106 ms 65536 KB Execution killed with signal 9
36 Incorrect 10 ms 2908 KB Output isn't correct
37 Incorrect 8 ms 2908 KB Output isn't correct
38 Runtime error 136 ms 65536 KB Execution killed with signal 9
39 Incorrect 9 ms 2904 KB Output isn't correct
40 Incorrect 9 ms 2908 KB Output isn't correct
41 Runtime error 136 ms 65536 KB Execution killed with signal 9
42 Incorrect 11 ms 2904 KB Output isn't correct
43 Incorrect 11 ms 2904 KB Output isn't correct
44 Runtime error 135 ms 65536 KB Execution killed with signal 9
45 Incorrect 15 ms 3164 KB Output isn't correct
46 Incorrect 13 ms 3164 KB Output isn't correct
47 Runtime error 133 ms 65536 KB Execution killed with signal 9
48 Incorrect 16 ms 3160 KB Output isn't correct
49 Incorrect 15 ms 3068 KB Output isn't correct
50 Runtime error 135 ms 65536 KB Execution killed with signal 9
51 Incorrect 19 ms 3160 KB Output isn't correct
52 Incorrect 21 ms 3348 KB Output isn't correct
53 Runtime error 140 ms 65536 KB Execution killed with signal 9
54 Incorrect 21 ms 3160 KB Output isn't correct
55 Incorrect 21 ms 3164 KB Output isn't correct
56 Runtime error 114 ms 65536 KB Execution killed with signal 9
57 Incorrect 26 ms 3408 KB Output isn't correct
58 Incorrect 27 ms 3420 KB Output isn't correct
59 Runtime error 143 ms 65536 KB Execution killed with signal 9
60 Incorrect 28 ms 3664 KB Output isn't correct
61 Incorrect 27 ms 3676 KB Output isn't correct
62 Runtime error 121 ms 65536 KB Execution killed with signal 9
63 Incorrect 104 ms 3680 KB Output isn't correct
64 Correct 156 ms 3680 KB Output is correct
65 Incorrect 123 ms 3564 KB Output isn't correct
66 Incorrect 112 ms 3688 KB Output isn't correct
67 Incorrect 128 ms 3668 KB Output isn't correct
68 Incorrect 51 ms 3480 KB Output isn't correct
69 Correct 47 ms 3676 KB Output is correct
70 Incorrect 39 ms 3512 KB Output isn't correct
71 Incorrect 41 ms 3512 KB Output isn't correct
72 Incorrect 38 ms 3664 KB Output isn't correct
73 Runtime error 218 ms 65536 KB Execution killed with signal 9
74 Runtime error 224 ms 65536 KB Execution killed with signal 9
75 Runtime error 225 ms 65536 KB Execution killed with signal 9
76 Runtime error 197 ms 65536 KB Execution killed with signal 9
77 Runtime error 224 ms 65536 KB Execution killed with signal 9
78 Runtime error 174 ms 65536 KB Execution killed with signal 9
79 Runtime error 196 ms 65536 KB Execution killed with signal 9
80 Runtime error 198 ms 65536 KB Execution killed with signal 9
81 Runtime error 195 ms 65536 KB Execution killed with signal 9
82 Runtime error 198 ms 65536 KB Execution killed with signal 9
83 Runtime error 182 ms 65536 KB Execution killed with signal 9
84 Runtime error 178 ms 65536 KB Execution killed with signal 9
85 Runtime error 175 ms 65536 KB Execution killed with signal 9
86 Runtime error 166 ms 65536 KB Execution killed with signal 9
87 Runtime error 178 ms 65536 KB Execution killed with signal 9
88 Runtime error 164 ms 65536 KB Execution killed with signal 9
89 Runtime error 145 ms 65536 KB Execution killed with signal 9
90 Runtime error 167 ms 65536 KB Execution killed with signal 9
91 Runtime error 164 ms 65536 KB Execution killed with signal 9
92 Runtime error 142 ms 65536 KB Execution killed with signal 9