Submission #1204759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204759		participant2510	Mecho (IOI09_mecho)	C++20	0 / 100	311 ms	131072 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define int long long
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define all(x) ((x).begin(), (x).end())

void solve()
{
    int n, s;
    cin >> n >> s;
    vector<string> v(n);
    for (auto &it : v)
        cin >> it;
    pii st;
    pii en;
    queue<pii> q;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            switch (v[i][j])
            {
            case 'M':
                st.first = i;
                st.second = j;
                break;
            case 'D':
                en.first = i;
                en.second = j;
                break;
            case 'H':
                q.push({i, j});
            }
        }
    }
    vii dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    auto val = [&](int a, int b)
    {
        if (a < 0 || b < 0 || a >= n || b >= n)
            return false;
        return true;
    };
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        if (v[x][y] == 'U')
            break;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i].first;
            int ny = y + dir[i].second;
            if (val(nx, ny) && (v[nx][ny] == 'G' || v[nx][ny] == 'M'))
            {
                q.push({nx, ny});
                v[nx][ny] = 'U';
            }
        }
    }
    int ans = -1;
    int l = 0;
    int r = (n * n + s - 1) / s;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        vector<string> grid = v;
        queue<pii> nq = q;
        for (int i = 0; i < mid; i++)
        {
            queue<pii> tmp = nq;
            while (!tmp.empty())
            {
                grid[tmp.front().first][tmp.front().second] = 'H';
                tmp.pop();
            }
            while (!nq.empty())
            {
                int x = nq.front().first;
                int y = nq.front().second;
                if (grid[x][y] == 'U')
                    break;
                nq.pop();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dir[i].first;
                    int ny = y + dir[i].second;
                    if (val(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M'))
                    {
                        nq.push({nx, ny});
                        grid[nx][ny] = 'U';
                    }
                }
            }
        }
        queue<pii> bear;
        bear.push(st);
        vvi dis(n, vi(n, INT32_MAX));
        dis[st.first][st.second] = 0;
        bool flag = false;
        while (1)
        {
            for (int i = 0; i < s; i++)
            {
                queue<pii> nbear;
                while (!bear.empty())
                {
                    int x = bear.front().first;
                    int y = bear.front().second;
                    bear.pop();
                    if (grid[x][y] == 'H')
                        continue;
                    for (int i = 0; i < 4; i++)
                    {
                        int nx = x + dir[i].first;
                        int ny = y + dir[i].second;
                        if (val(nx, ny) && grid[nx][ny] == 'G' || grid[nx][ny] == 'D' || grid[nx][ny] == 'U' && dis[nx][ny] == INT32_MAX)
                        {
                            nbear.push({nx, ny});
                            dis[nx][ny] = dis[x][y] + 1;
                            if (nx == en.first && ny == en.second)
                            {
                                flag = true;
                                break;
                            }
                        }
                    }
                    if (flag)
                        break;
                }
                bear = nbear;
            }

            if (bear.size() == 0)
                break;
            if (flag)
                break;

            queue<pii> tmp = nq;
            while (!tmp.empty())
            {
                grid[tmp.front().first][tmp.front().second] = 'H';
                tmp.pop();
            }
            while (!nq.empty())
            {
                int x = nq.front().first;
                int y = nq.front().second;
                if (grid[x][y] == 'U')
                    break;
                nq.pop();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dir[i].first;
                    int ny = y + dir[i].second;
                    if (val(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M'))
                    {
                        nq.push({nx, ny});
                        grid[nx][ny] = 'U';
                    }
                }
            }
        }
        if (flag)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

• Subtask 1: 0 / 100