Submission #888542

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888542	2023-12-17T17:19:53 Z	Billy_Nguyen	Mecho (IOI09_mecho)	C++17	6 / 100	124 ms	27680 KB

mecho

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

#define x first
#define fastio()                 \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004;  // Modular inverse of 2 modulo (10^9 + 7), also
                                // the number has to be in long long otherwise
                                // if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
vector<vector<char>> grid;
ll n, s;
pair<ll, ll> bear, home;
vector<pair<ll, ll>> hives;
vector<vector<ll>> beesDepths;
vector<vector<ll>> bearDepths;
bool valid = false;

void floodfill(ll i, ll j, vector<vector<bool>> &visited, ll mins) {
    REP(k, 0, 4) {
        if (i + dy[k] < 1 || j + dx[k] < 1 || i + dy[k] > n || j + dx[k] > n) {
            continue;
        }

        if (visited[i + dy[k]][j + dx[k]]) {
            continue;
        }

        if ((bearDepths[i + dy[k]][j + dx[k]] + 1) / s >=
            beesDepths[i + dy[k]][j + dx[k]] - mins) {
            continue;
        }

        if (grid[i + dy[k]][j + dx[k]] == 'D') {
            valid = true;
            return;
        }

        if (grid[i + dy[k]][j + dx[k]] != 'G') {
            continue;
        }

        visited[i][j] = true;
        floodfill(i + dy[k], j + dx[k], visited, mins);
    }
}

void solve() {
    cin >> n >> s;

    grid.resize(n + 1);
    beesDepths.resize(n + 1);

    REP(i, 0, n + 1) {
        grid[i].resize(n + 1);
        beesDepths[i].resize(n + 1, 1e18);
    }

    REP(i, 1, n + 1) {
        REP(j, 1, n + 1) {
            cin >> grid[i][j];

            if (grid[i][j] == 'M') {
                bear = {i, j};
            }

            if (grid[i][j] == 'D') {
                home = {i, j};
            }

            if (grid[i][j] == 'H') {
                hives.PB({i, j});
            }
        }
    }

    deque<pair<pair<ll, ll>, ll>> q;

    REP(i, 0, hives.size()) {
        q.PB(MP(hives[i], 0));
        beesDepths[hives[i].x][hives[i].y] = 0;
    }

    while (!q.empty()) {
        pair<pair<ll, ll>, ll> cur = q.front();
        pair<ll, ll> coords = cur.x;
        ll d = cur.y;
        q.pop_front();

        REP(k, 0, 4) {
            if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
                coords.x + dy[k] > n || coords.y + dy[k] > n ||
                (grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' &&
                 grid[coords.x + dy[k]][coords.y + dx[k]] != 'D' && grid[coords.x + dy[k]][coords.y + dx[k]] != 'M')) {
                continue;
            }

            if (beesDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) {
                beesDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
                q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
            }
        }
    }

    ll l = 0;
    ll r = n * n;
    q.PB(MP(bear, 0));
    bearDepths.resize(n + 1);

    REP(i, 0, n + 1) { bearDepths[i].resize(n + 1, 1e18); }
    bearDepths[bear.x][bear.y] = 0;

    while (!q.empty()) {
        pair<pair<ll, ll>, ll> cur = q.front();
        q.pop_front();

        pair<ll, ll> coords = cur.x;
        ll d = cur.y;

        REP(k, 0, 4) {
            if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
                coords.x + dy[k] > n || coords.y + dy[k] > n ||
                (grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' &&
                 grid[coords.x + dy[k]][coords.y + dx[k]] != 'D')) {
                continue;
            }

            if (bearDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) {
                bearDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
                q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
            }
        }
    }

    while (l <= r) {
        ll mid = l + (r - l) / 2;
        vector<vector<bool>> bearVis(n + 1);

        REP(i, 0, n + 1) { bearVis[i].resize(n + 1, false); }

        bearVis[bear.x][bear.y] = true;

        floodfill(bear.x, bear.y, bearVis, mid);
        if (valid) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }

        // cout << l << " " << r << "\n";
    }

    cout << l - 1 << "\n";
}

int main() {
    fastio();
    solve();

    return 0;
}

Compilation message

mecho.cpp: In function 'void solve()':
mecho.cpp:32:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 | #define REP(i, a, b) for (int i = a; i < b; i++)
......
  109 |     REP(i, 0, hives.size()) {
      |         ~~~~~~~~~~~~~~~~~~              
mecho.cpp:109:5: note: in expansion of macro 'REP'
  109 |     REP(i, 0, hives.size()) {
      |     ^~~

Subtask #1

6.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	Output isn't correct
2	Incorrect	1 ms	600 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Correct	0 ms	348 KB	Output is correct
6	Incorrect	0 ms	348 KB	Output isn't correct
7	Incorrect	101 ms	25540 KB	Output isn't correct
8	Correct	0 ms	348 KB	Output is 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	0 ms	348 KB	Output isn't correct
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Correct	1 ms	604 KB	Output is correct
15	Incorrect	0 ms	348 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	1 ms	348 KB	Output isn't correct
19	Incorrect	0 ms	348 KB	Output isn't correct
20	Incorrect	0 ms	344 KB	Output isn't correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Incorrect	1 ms	344 KB	Output isn't correct
23	Incorrect	0 ms	348 KB	Output isn't correct
24	Incorrect	0 ms	348 KB	Output isn't correct
25	Incorrect	0 ms	348 KB	Output isn't correct
26	Incorrect	1 ms	348 KB	Output isn't correct
27	Incorrect	1 ms	348 KB	Output isn't correct
28	Incorrect	1 ms	604 KB	Output isn't correct
29	Incorrect	1 ms	348 KB	Output isn't correct
30	Incorrect	1 ms	604 KB	Output isn't correct
31	Incorrect	1 ms	348 KB	Output isn't correct
32	Incorrect	1 ms	604 KB	Output isn't correct
33	Incorrect	4 ms	2592 KB	Output isn't correct
34	Incorrect	13 ms	5212 KB	Output isn't correct
35	Incorrect	11 ms	2652 KB	Output isn't correct
36	Incorrect	5 ms	3040 KB	Output isn't correct
37	Incorrect	17 ms	6748 KB	Output isn't correct
38	Incorrect	16 ms	3164 KB	Output isn't correct
39	Incorrect	6 ms	3932 KB	Output isn't correct
40	Incorrect	21 ms	8424 KB	Output isn't correct
41	Incorrect	19 ms	3928 KB	Output isn't correct
42	Incorrect	7 ms	4700 KB	Output isn't correct
43	Incorrect	26 ms	10380 KB	Output isn't correct
44	Incorrect	24 ms	4700 KB	Output isn't correct
45	Incorrect	8 ms	5724 KB	Output isn't correct
46	Incorrect	31 ms	12640 KB	Output isn't correct
47	Incorrect	30 ms	5724 KB	Output isn't correct
48	Incorrect	12 ms	6492 KB	Output isn't correct
49	Incorrect	46 ms	14980 KB	Output isn't correct
50	Incorrect	35 ms	6804 KB	Output isn't correct
51	Incorrect	12 ms	7772 KB	Output isn't correct
52	Incorrect	47 ms	17244 KB	Output isn't correct
53	Incorrect	41 ms	7844 KB	Output isn't correct
54	Incorrect	14 ms	8792 KB	Output isn't correct
55	Incorrect	63 ms	20356 KB	Output isn't correct
56	Incorrect	47 ms	9052 KB	Output isn't correct
57	Incorrect	15 ms	10072 KB	Output isn't correct
58	Incorrect	68 ms	23100 KB	Output isn't correct
59	Incorrect	59 ms	10280 KB	Output isn't correct
60	Incorrect	18 ms	11352 KB	Output isn't correct
61	Incorrect	80 ms	26252 KB	Output isn't correct
62	Incorrect	67 ms	11552 KB	Output isn't correct
63	Incorrect	96 ms	11548 KB	Output isn't correct
64	Incorrect	101 ms	11548 KB	Output isn't correct
65	Incorrect	124 ms	11480 KB	Output isn't correct
66	Incorrect	114 ms	11548 KB	Output isn't correct
67	Correct	109 ms	11348 KB	Output is correct
68	Correct	58 ms	11616 KB	Output is correct
69	Incorrect	49 ms	11600 KB	Output isn't correct
70	Incorrect	49 ms	11504 KB	Output isn't correct
71	Correct	55 ms	11604 KB	Output is correct
72	Incorrect	43 ms	11348 KB	Output isn't correct
73	Incorrect	57 ms	26928 KB	Output isn't correct
74	Incorrect	53 ms	21312 KB	Output isn't correct
75	Incorrect	75 ms	23628 KB	Output isn't correct
76	Incorrect	76 ms	21076 KB	Output isn't correct
77	Incorrect	59 ms	21684 KB	Output isn't correct
78	Correct	95 ms	27680 KB	Output is correct
79	Incorrect	46 ms	20304 KB	Output isn't correct
80	Incorrect	63 ms	22612 KB	Output isn't correct
81	Incorrect	92 ms	25364 KB	Output isn't correct
82	Incorrect	71 ms	23892 KB	Output isn't correct
83	Correct	74 ms	17116 KB	Output is correct
84	Incorrect	66 ms	16792 KB	Output isn't correct
85	Incorrect	75 ms	17572 KB	Output isn't correct
86	Incorrect	76 ms	17232 KB	Output isn't correct
87	Incorrect	79 ms	18012 KB	Output isn't correct
88	Correct	79 ms	18768 KB	Output is correct
89	Incorrect	80 ms	18004 KB	Output isn't correct
90	Incorrect	83 ms	19284 KB	Output isn't correct
91	Incorrect	86 ms	18748 KB	Output isn't correct
92	Incorrect	83 ms	18772 KB	Output isn't correct