oj.uz

Submission #100780

# Submission time Handle Problem Language Result Execution time Memory
100780 2019-03-14T10:12:00 Z Alexa2001 Mecho (IOI09_mecho) C++17
30 / 100
 347 ms 66560 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 808, inf = Nmax * Nmax;
int n, S;
char a[Nmax][Nmax];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int tmp[Nmax][Nmax], D[Nmax][Nmax];
queue< pair<int,int> > q;


void prec()
{
    int i, j, x, y, X, Y;

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            tmp[i][j] = inf;

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            if(a[i][j] == 'H')
            {
                q.push({i, j});
                tmp[i][j] = 0;
            }

    while(q.size())
    {
        tie(x, y) = q.front();
        q.pop();

        for(i=0; i<4; ++i)
        {
            X = x + dx[i];
            Y = y + dy[i];

            if((a[X][Y] == 'G' || a[X][Y] == 'M') && tmp[X][Y] == inf)
            {
                tmp[X][Y] = tmp[x][y] + 1;
                q.push({X, Y});
            }
        }
    }
}

bool check(int T)
{
    while(q.size()) q.pop();

    int i, j, x, y, X, Y;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
        {
            if(a[i][j] == 'M')
                x = i, y = j;
            D[i][j] = inf;
        }

    if(!(T < tmp[x][y])) return 0;

    q.push({x, y});
    D[x][y] = 0;

    while(q.size())
    {
        tie(X, Y) = q.front();
        q.pop();

        for(i=0; i<4; ++i)
        {
            x = X + dx[i];
            y = Y + dy[i];

            if(a[x][y] == 'D') return 1;

            if(a[x][y] == 'G' && D[X][Y] + 1 < S * (tmp[x][y] - T))
            {
                D[x][y] = D[X][Y] + 1;
                q.push({x, y});
            }
        }
    }
    return 0;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n >> S;
    int i;
    for(i=1; i<=n; ++i) cin >> (a[i] + 1);

    prec();

    int st, dr, mid;
    st = 0; dr = n * n;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(mid)) st = mid + 1;
            else dr = mid - 1;
    }
    cout << dr << '\n';

    return 0;
}

Compilation message

mecho.cpp: In function 'bool check(int)':
mecho.cpp:64:22: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(!(T < tmp[x][y])) return 0;
              ~~~~~~~~^
mecho.cpp:64:22: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Runtime error 209 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 2 ms 384 KB Output is correct
9 Correct 31 ms 6932 KB Output is correct
10 Correct 19 ms 2304 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Runtime error 204 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 204 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Correct 2 ms 512 KB Output is correct
16 Runtime error 347 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 2 ms 512 KB Output is correct
18 Runtime error 270 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 3 ms 640 KB Output is correct
20 Runtime error 345 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Correct 4 ms 640 KB Output is correct
22 Runtime error 318 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Correct 3 ms 768 KB Output is correct
24 Runtime error 290 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Correct 4 ms 768 KB Output is correct
26 Runtime error 331 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Correct 3 ms 768 KB Output is correct
28 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Correct 3 ms 896 KB Output is correct
30 Runtime error 338 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Correct 3 ms 896 KB Output is correct
32 Runtime error 310 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Correct 9 ms 2816 KB Output is correct
34 Runtime error 271 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 292 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Correct 9 ms 3200 KB Output is correct
37 Runtime error 297 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 262 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 9 ms 3584 KB Output is correct
40 Runtime error 253 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 239 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Correct 11 ms 3940 KB Output is correct
43 Runtime error 288 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Runtime error 285 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Correct 18 ms 4224 KB Output is correct
46 Runtime error 292 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 241 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Correct 14 ms 4608 KB Output is correct
49 Runtime error 293 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 307 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Correct 18 ms 4992 KB Output is correct
52 Runtime error 285 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 320 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Correct 25 ms 5376 KB Output is correct
55 Runtime error 305 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 324 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Correct 23 ms 5880 KB Output is correct
58 Runtime error 294 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 309 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Correct 24 ms 6016 KB Output is correct
61 Runtime error 272 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 285 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 266 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 301 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 311 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 295 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 305 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 300 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 273 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 274 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 265 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 259 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 243 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 206 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 209 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 229 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 218 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 199 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 216 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 283 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 220 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 219 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 224 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 219 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 271 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 222 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 221 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 240 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 209 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 226 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 249 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 229 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)