oj.uz

Submission #100779

# Submission time Handle Problem Language Result Execution time Memory
100779 2019-03-14T10:07:35 Z Alexa2001 Mecho (IOI09_mecho) C++17
30 / 100
 368 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];



void prec()
{
    int i, j, x, y, X, Y;
    queue< pair<int,int> > q;

    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)
{
    queue< pair<int,int> > q;

    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:66:22: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(!(T < tmp[x][y])) return 0;
              ~~~~~~~~^
mecho.cpp:66: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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Runtime error 232 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 3 ms 512 KB Output is correct
9 Correct 27 ms 6924 KB Output is correct
10 Correct 13 ms 2432 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Runtime error 206 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 221 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 306 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 259 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 258 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Correct 2 ms 640 KB Output is correct
22 Runtime error 287 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Correct 2 ms 768 KB Output is correct
24 Runtime error 283 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Correct 3 ms 768 KB Output is correct
26 Runtime error 268 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Correct 2 ms 768 KB Output is correct
28 Runtime error 264 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 268 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Correct 2 ms 896 KB Output is correct
32 Runtime error 267 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Correct 10 ms 2972 KB Output is correct
34 Runtime error 288 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 249 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Correct 8 ms 3328 KB Output is correct
37 Runtime error 277 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 245 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 9 ms 3712 KB Output is correct
40 Runtime error 283 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 302 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Correct 13 ms 4224 KB Output is correct
43 Runtime error 314 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Runtime error 295 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Correct 15 ms 4608 KB Output is correct
46 Runtime error 287 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 277 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Correct 17 ms 4992 KB Output is correct
49 Runtime error 283 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 313 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Correct 18 ms 5368 KB Output is correct
52 Runtime error 248 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 251 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Correct 19 ms 5760 KB Output is correct
55 Runtime error 368 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 282 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Correct 21 ms 6272 KB Output is correct
58 Runtime error 287 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 295 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Correct 24 ms 6648 KB Output is correct
61 Runtime error 277 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 269 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 271 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 256 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 267 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 248 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 267 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 285 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 272 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 266 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 303 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 249 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 198 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 204 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 198 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 214 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 199 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 243 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 217 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 190 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 233 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 206 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 218 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 231 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 238 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 201 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 213 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 218 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 230 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 214 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 264 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 210 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)