Submission #1161627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161627		misavo	Mecho (IOI09_mecho)	C++20	100 / 100	116 ms	22248 KiB

mecho

#include <bits/stdc++.h>
// #include <iostream>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x << " " <<endl;
#define printp(a) for(auto x : a) cout << x.first << " " << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll t, n, m, s, k, a, b, tot;
char mat[1000][1000];
bool visited[1000][1000];

void solve() {
    cin >> n >> s;
    f(i, 0, n) f(j, 0, n) cin >> mat[i][j];

    vector<vpl> bees;
    queue<pll> q;
    f(i, 0, n) {
        f(j, 0, n) {
            if (mat[i][j] == 'H') {
                visited[i][j] = 1;
                q.push({i, j});
            }
        }
    }

    vpl vec;
    ll cnt = q.size();
    while (!q.empty()) {
        pll curr = q.front();
        vec.pb(curr);
        q.pop();

        ll x = curr.F, y = curr.S;
        if (x > 0 && !visited[x-1][y]) {
            if (mat[x-1][y] == 'G' || mat[x-1][y] == 'M') q.push({x-1, y});
            visited[x-1][y] = 1;
        }
        if (x < n-1 && !visited[x+1][y]) {
            if (mat[x+1][y] == 'G' || mat[x+1][y] == 'M') q.push({x+1, y});
            visited[x+1][y] = 1;
        }
        if (y > 0 && !visited[x][y-1]) {
            if (mat[x][y-1] == 'G' || mat[x][y-1] == 'M') q.push({x, y-1});
            visited[x][y-1] = 1;
        }
        if (y < n-1 && !visited[x][y+1]) {
            if (mat[x][y+1] == 'G' || mat[x][y+1] == 'M') q.push({x, y+1});
            visited[x][y+1] = 1;
        }
        
        cnt--;
        if (cnt == 0) {
            bees.pb(vec);
            vec.clear();
            cnt = q.size();
        }
    }

    pll start;
    f(i, 0, n) f(j, 0, n) if (mat[i][j] == 'M') {start = {i, j}; break;}

    ll l = 0, r = bees.size() - 1;
    tot = -1;
    while (l <= r) {
        ll m = (l + r) / 2;

        vector<vb> visited(n, vb(n, 0));
        vector<vb> infect(n, vb(n, 0));
        cf(i, 0, m) for (pll bee : bees[i]) infect[bee.F][bee.S] = 1;

        queue<pll> q;
        q.push(start);
        visited[start.F][start.S] = 1;
        bool reach = false;
        ll mv = 0, cnt = 1;
        while (!q.empty()) {
            pll curr = q.front();
            q.pop();

            ll x = curr.F, y = curr.S;
            if (!infect[x][y]) {
                if (x > 0 && !visited[x-1][y]) {
                    if (mat[x-1][y] == 'D') {
                        reach = true;
                        break;
                    } else if (mat[x-1][y] == 'G') q.push({x-1, y});
                    visited[x-1][y] = 1;
                }
                if (x < n-1 && !visited[x+1][y]) {
                    if (mat[x+1][y] == 'D') {
                        reach = true;
                        break;
                    } else if (mat[x+1][y] == 'G') q.push({x+1, y});
                    visited[x+1][y] = 1;
                }
                if (y > 0 && !visited[x][y-1]) {
                    if (mat[x][y-1] == 'D') {
                        reach = true;
                        break;
                    } else if (mat[x][y-1] == 'G') q.push({x, y-1});
                    visited[x][y-1] = 1;
                }
                if (y < n-1 && !visited[x][y+1]) {
                    if (mat[x][y+1] == 'D') {
                        reach = true;
                        break;
                    } else if (mat[x][y+1] == 'G') q.push({x, y+1});
                    visited[x][y+1] = 1;
                }
            }

            cnt--;
            if (cnt == 0) {
                mv++;
                cnt = q.size();
                if (mv % s == 0) {
                    for (pll bee : bees[m + mv/s]) infect[bee.F][bee.S] = 1;
                }
            } 
        }

        if (reach) {
            l = m + 1;
            tot = m;
        } else r = m - 1;
    } cout << tot <<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    t = 1;
    while (t--) {
        solve();
    }
}

• Subtask 1: 100 / 100