oj.uz

Submission #839386

# Submission time Handle Problem Language Result Execution time Memory
839386 2023-08-29T23:03:43 Z ArashJafariyan Mecho (IOI09_mecho) C++17
0 / 100
 549 ms 6860 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define pb push_back
#define size(a) (int) a.size()
#define all(a) a.begin(), a.end()

const int maxn = 800 + 4, inf = 1e8;

int n, s, mx, my, dx, dy, d[maxn][maxn], save[maxn][maxn];
bitset<maxn> vis[maxn];
string a[maxn];
queue<array<int, 2>> q;

void rest() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            vis[i][j] = 0;
            d[i][j] = inf;
        }
    }
    return;
}

bool check0(int x, int y, int dis) {
    bool ret = (0 <= x && x < n);
    ret &= (0 <= y && y < n);
    if (ret) {
        ret &= !vis[x][y];
        ret &= (a[x][y] == 'G' || a[x][y] == 'M');
    }
    return ret;
}

void upd0(int x, int y) { 
    int dis = d[x][y] + 1;

    if (check0(x - 1, y, dis)) {
        vis[x - 1][y] = 1;
        d[x - 1][y] = dis;
        q.push({x - 1, y});
    }
    if (check0(x + 1, y, dis)) {
        vis[x + 1][y] = 1;
        d[x + 1][y] = dis;
        q.push({x + 1, y});
    }
    if (check0(x, y - 1, dis)) {
        vis[x][y - 1] = 1;
        d[x][y - 1] = dis;
        q.push({x, y - 1});
    }
    if (check0(x, y + 1, dis)) {
        vis[x][y + 1] = 1;
        d[x][y + 1] = dis;
        q.push({x, y + 1});
    }
}

bool check1(int x, int y, int dis, int k) {
    bool ret = (0 <= x && x < n);
    ret &= (0 <= y && y < n);
    if (ret) {
        ret &= !vis[x][y];
        ret &= a[x][y] == 'G' || a[x][y] == 'D';
        ret &= (dis + s - 1) / s <= save[x][y] - k;
    }
    return ret;
}

void upd1(int x, int y, int k) {
    int dis = d[x][y] + 1;
    
    if (check1(x - 1, y, dis, k)) {
        vis[x - 1][y] = 1;
        d[x - 1][y] = dis;
        q.push({x - 1, y});
    }
    if (check1(x + 1, y, dis, k)) {
        vis[x + 1][y] = 1;
        d[x + 1][y] = dis;
        q.push({x + 1, y});
    }
    if (check1(x, y - 1, dis, k)) {
        vis[x][y - 1] = 1;
        d[x][y - 1] = dis;
        q.push({x, y - 1});
    }
    if (check1(x, y + 1, dis, k)) {
        vis[x][y + 1] = 1;
        d[x][y + 1] = dis;
        q.push({x, y + 1});
    }
}

bool bfs(int k) {
    rest();

    if (save[mx][my] <= k) {
        return 0;
    }

    d[mx][my] = 0;
    vis[mx][my] = 1;
    q.push({mx, my});
    while (!q.empty()) {
        array<int, 2> v = q.front();
        q.pop();
        upd1(v[0], v[1], k);
    }
    
    return d[dx][dy] != inf;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

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

    while (!q.empty()) {
        array<int, 2> v = q.front();
        q.pop();
        upd0(v[0], v[1]);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (a[i][j] == 'M') {
                mx = i;
                my = j;
            }
            if (a[i][j] == 'D') {
                dx = i;
                dy = j;
            }
            save[i][j] = d[i][j];
        }
    }

    int l, r;
    l = -1;
    r = inf;

    while (r - l > 1) {
        int m = (l + r) >> 1;
        if (bfs(m)) {
            l = m;
        }
        else {
            r = m;
        }
    }
    cout << l << '\n';

    return 0;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 549 ms 6616 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Incorrect 2 ms 736 KB Output isn't correct
13 Incorrect 3 ms 596 KB Output isn't correct
14 Incorrect 4 ms 724 KB Output isn't correct
15 Incorrect 1 ms 596 KB Output isn't correct
16 Incorrect 1 ms 468 KB Output isn't correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Incorrect 2 ms 468 KB Output isn't correct
19 Incorrect 1 ms 468 KB Output isn't correct
20 Incorrect 1 ms 468 KB Output isn't correct
21 Incorrect 1 ms 596 KB Output isn't correct
22 Incorrect 2 ms 596 KB Output isn't correct
23 Incorrect 2 ms 596 KB Output isn't correct
24 Incorrect 2 ms 596 KB Output isn't correct
25 Incorrect 2 ms 724 KB Output isn't correct
26 Incorrect 2 ms 724 KB Output isn't correct
27 Incorrect 2 ms 724 KB Output isn't correct
28 Incorrect 3 ms 724 KB Output isn't correct
29 Incorrect 3 ms 724 KB Output isn't correct
30 Incorrect 3 ms 724 KB Output isn't correct
31 Incorrect 3 ms 740 KB Output isn't correct
32 Incorrect 3 ms 852 KB Output isn't correct
33 Incorrect 52 ms 2772 KB Output isn't correct
34 Incorrect 52 ms 2772 KB Output isn't correct
35 Incorrect 77 ms 2896 KB Output isn't correct
36 Incorrect 67 ms 3156 KB Output isn't correct
37 Incorrect 69 ms 3156 KB Output isn't correct
38 Incorrect 95 ms 3228 KB Output isn't correct
39 Incorrect 87 ms 3540 KB Output isn't correct
40 Incorrect 87 ms 3640 KB Output isn't correct
41 Incorrect 122 ms 3540 KB Output isn't correct
42 Incorrect 104 ms 4052 KB Output isn't correct
43 Incorrect 108 ms 4036 KB Output isn't correct
44 Incorrect 155 ms 4052 KB Output isn't correct
45 Incorrect 124 ms 4460 KB Output isn't correct
46 Incorrect 128 ms 4460 KB Output isn't correct
47 Incorrect 183 ms 4472 KB Output isn't correct
48 Incorrect 147 ms 4904 KB Output isn't correct
49 Incorrect 157 ms 4940 KB Output isn't correct
50 Incorrect 224 ms 4912 KB Output isn't correct
51 Incorrect 175 ms 5452 KB Output isn't correct
52 Incorrect 179 ms 5332 KB Output isn't correct
53 Incorrect 252 ms 5336 KB Output isn't correct
54 Incorrect 200 ms 5716 KB Output isn't correct
55 Incorrect 214 ms 5716 KB Output isn't correct
56 Incorrect 314 ms 5716 KB Output isn't correct
57 Incorrect 227 ms 6108 KB Output isn't correct
58 Incorrect 242 ms 6108 KB Output isn't correct
59 Incorrect 353 ms 6092 KB Output isn't correct
60 Incorrect 273 ms 6512 KB Output isn't correct
61 Incorrect 275 ms 6508 KB Output isn't correct
62 Incorrect 401 ms 6512 KB Output isn't correct
63 Incorrect 464 ms 6484 KB Output isn't correct
64 Incorrect 466 ms 6508 KB Output isn't correct
65 Incorrect 464 ms 6512 KB Output isn't correct
66 Incorrect 504 ms 6512 KB Output isn't correct
67 Incorrect 464 ms 6516 KB Output isn't correct
68 Incorrect 460 ms 6484 KB Output isn't correct
69 Incorrect 456 ms 6532 KB Output isn't correct
70 Incorrect 460 ms 6540 KB Output isn't correct
71 Incorrect 490 ms 6536 KB Output isn't correct
72 Incorrect 431 ms 6476 KB Output isn't correct
73 Incorrect 533 ms 6784 KB Output isn't correct
74 Incorrect 503 ms 6788 KB Output isn't correct
75 Incorrect 513 ms 6860 KB Output isn't correct
76 Incorrect 497 ms 6788 KB Output isn't correct
77 Incorrect 490 ms 6860 KB Output isn't correct
78 Incorrect 526 ms 6760 KB Output isn't correct
79 Incorrect 514 ms 6752 KB Output isn't correct
80 Incorrect 511 ms 6756 KB Output isn't correct
81 Incorrect 502 ms 6756 KB Output isn't correct
82 Incorrect 510 ms 6760 KB Output isn't correct
83 Incorrect 489 ms 6716 KB Output isn't correct
84 Incorrect 532 ms 6724 KB Output isn't correct
85 Incorrect 521 ms 6732 KB Output isn't correct
86 Incorrect 507 ms 6720 KB Output isn't correct
87 Incorrect 521 ms 6720 KB Output isn't correct
88 Incorrect 539 ms 6664 KB Output isn't correct
89 Incorrect 509 ms 6728 KB Output isn't correct
90 Incorrect 518 ms 6668 KB Output isn't correct
91 Incorrect 548 ms 6672 KB Output isn't correct
92 Incorrect 527 ms 6672 KB Output isn't correct