Submission #888469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888469	2023-12-17T13:43:33 Z	Billy_Nguyen	Mecho (IOI09_mecho)	C++17	0 / 100	169 ms	28240 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')
            {
                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')
            {
                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);
        valid = false;

        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++)
......
  125 |     REP(i, 0, hives.size())
      |         ~~~~~~~~~~~~~~~~~~              
mecho.cpp:125:5: note: in expansion of macro 'REP'
  125 |     REP(i, 0, hives.size())
      |     ^~~

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Output isn't correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	0 ms	344 KB	Output isn't correct
4	Incorrect	0 ms	344 KB	Output isn't correct
5	Incorrect	0 ms	348 KB	Output isn't correct
6	Incorrect	0 ms	456 KB	Output isn't correct
7	Incorrect	116 ms	26256 KB	Output isn't correct
8	Incorrect	0 ms	344 KB	Output isn't correct
9	Incorrect	0 ms	344 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	Incorrect	1 ms	604 KB	Output isn't 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	0 ms	348 KB	Output isn't correct
19	Incorrect	0 ms	348 KB	Output isn't correct
20	Incorrect	1 ms	344 KB	Output isn't correct
21	Incorrect	1 ms	348 KB	Output isn't correct
22	Incorrect	1 ms	348 KB	Output isn't correct
23	Incorrect	1 ms	348 KB	Output isn't correct
24	Incorrect	1 ms	344 KB	Output isn't correct
25	Incorrect	1 ms	344 KB	Output isn't correct
26	Incorrect	1 ms	604 KB	Output isn't correct
27	Incorrect	1 ms	348 KB	Output isn't correct
28	Incorrect	1 ms	464 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	2652 KB	Output isn't correct
34	Incorrect	16 ms	5468 KB	Output isn't correct
35	Incorrect	11 ms	2844 KB	Output isn't correct
36	Incorrect	5 ms	3420 KB	Output isn't correct
37	Incorrect	34 ms	7004 KB	Output isn't correct
38	Incorrect	15 ms	3416 KB	Output isn't correct
39	Incorrect	7 ms	4188 KB	Output isn't correct
40	Incorrect	31 ms	8796 KB	Output isn't correct
41	Incorrect	20 ms	4268 KB	Output isn't correct
42	Incorrect	8 ms	4956 KB	Output isn't correct
43	Incorrect	51 ms	10560 KB	Output isn't correct
44	Incorrect	27 ms	4956 KB	Output isn't correct
45	Incorrect	10 ms	5980 KB	Output isn't correct
46	Incorrect	43 ms	12880 KB	Output isn't correct
47	Incorrect	36 ms	6088 KB	Output isn't correct
48	Incorrect	11 ms	7000 KB	Output isn't correct
49	Incorrect	65 ms	15212 KB	Output isn't correct
50	Incorrect	35 ms	7004 KB	Output isn't correct
51	Incorrect	12 ms	7980 KB	Output isn't correct
52	Incorrect	70 ms	17752 KB	Output isn't correct
53	Incorrect	41 ms	8272 KB	Output isn't correct
54	Incorrect	16 ms	9412 KB	Output isn't correct
55	Incorrect	106 ms	20696 KB	Output isn't correct
56	Incorrect	49 ms	9524 KB	Output isn't correct
57	Incorrect	19 ms	10708 KB	Output isn't correct
58	Incorrect	105 ms	23444 KB	Output isn't correct
59	Incorrect	62 ms	10832 KB	Output isn't correct
60	Incorrect	23 ms	12160 KB	Output isn't correct
61	Incorrect	153 ms	26704 KB	Output isn't correct
62	Incorrect	67 ms	12124 KB	Output isn't correct
63	Incorrect	97 ms	12112 KB	Output isn't correct
64	Incorrect	169 ms	12260 KB	Output isn't correct
65	Incorrect	153 ms	12260 KB	Output isn't correct
66	Incorrect	126 ms	12088 KB	Output isn't correct
67	Incorrect	109 ms	12180 KB	Output isn't correct
68	Incorrect	62 ms	12372 KB	Output isn't correct
69	Incorrect	53 ms	12112 KB	Output isn't correct
70	Incorrect	49 ms	12252 KB	Output isn't correct
71	Incorrect	52 ms	12112 KB	Output isn't correct
72	Incorrect	56 ms	11752 KB	Output isn't correct
73	Incorrect	102 ms	24108 KB	Output isn't correct
74	Incorrect	80 ms	21940 KB	Output isn't correct
75	Incorrect	91 ms	24476 KB	Output isn't correct
76	Incorrect	75 ms	21588 KB	Output isn't correct
77	Incorrect	78 ms	22528 KB	Output isn't correct
78	Incorrect	93 ms	28240 KB	Output isn't correct
79	Incorrect	82 ms	20816 KB	Output isn't correct
80	Incorrect	69 ms	22992 KB	Output isn't correct
81	Incorrect	82 ms	25680 KB	Output isn't correct
82	Incorrect	75 ms	24468 KB	Output isn't correct
83	Incorrect	78 ms	17744 KB	Output isn't correct
84	Incorrect	73 ms	17236 KB	Output isn't correct
85	Incorrect	75 ms	18156 KB	Output isn't correct
86	Incorrect	80 ms	18164 KB	Output isn't correct
87	Incorrect	81 ms	18852 KB	Output isn't correct
88	Incorrect	80 ms	19536 KB	Output isn't correct
89	Incorrect	85 ms	18556 KB	Output isn't correct
90	Incorrect	82 ms	19848 KB	Output isn't correct
91	Incorrect	109 ms	19532 KB	Output isn't correct
92	Incorrect	93 ms	19284 KB	Output isn't correct