Submission #1176180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176180		AMel0n	Mecho (IOI09_mecho)	C++20	100 / 100	176 ms	7824 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define ll long long
#define FOR(N) for(int i = 0; i < N; ++i)
#define pi pair<int,int>
#define vi vector<int>
#define F first
#define S second



int N, SPS;
string input;
vector<vector<char>> grid;  //  j+y vertical, i+x horizontal
pi start, endp;
vi dx = {1,0,-1,0};
vi dy = {0,-1,0,1};
vector<vi> bees;




signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> SPS;
    grid.resize(N, vector<char>(N));
    bees.resize(N, vi(N, -1));


    queue<pair<int,pi>> bfsbee;

    for(int j = 0; j < N; ++j) {
        cin >> input;
        FOR(N) {
            grid[i][j] = input[i];
            if (input[i] == 'M') start = {i,j};
            if (input[i] == 'D') endp = {i,j};
            if (input[i] == 'H') bfsbee.push({0,{i,j}});
            //cout << input[i] << endl;
        }
    }

    while(bfsbee.size()) {
        int t = bfsbee.front().F;
        int x = bfsbee.front().S.F;
        int y = bfsbee.front().S.S;
        //cout << x << ' ' << y << ' ' << t << endl;
        bfsbee.pop();
        if (bees[x][y] != -1) continue;
        bees[x][y] = t;
        FOR(4) {
            int bruh1 = x + dx[i];
            int bruh2 = y + dy[i];
            if (bruh1 >= N || bruh2 >= N || bruh1 < 0 || bruh2 < 0) continue;

            if (grid[bruh1][bruh2] == 'T' || grid[bruh1][bruh2] == 'D' || bees[bruh1][bruh2] != -1) continue;
            bfsbee.push({t+1, {bruh1, bruh2}});
        } 
    }

    int l = -1; int r = 1000000;
    while (l != r - 1) {
        int m = (l + r) / 2;
        bool can = false;
        queue<pair<int,pi>> bfs; // SPS, pos
        bfs.push({0, start});
        vector<vector<bool>> vis(N, vector<bool>(N));
        while(bfs.size()) {
            int steps = bfs.front().F;
            int x = bfs.front().S.F;
            int y = bfs.front().S.S;
            bfs.pop();
            if (vis[x][y]) continue;
            vis[x][y] = true;
            if (endp == make_pair(x, y)) {can = true; break;}
            if (m + steps / SPS >= bees[x][y]) continue;
            FOR(4) {
                int bruh1 = x + dx[i];
                int bruh2 = y + dy[i];
                if (bruh1 >= N || bruh2 >= N || bruh1 < 0 || bruh2 < 0) continue;

                if (grid[bruh1][bruh2] == 'T' || grid[bruh1][bruh2] == 'H') continue;
                bfs.push({steps+1, {bruh1, bruh2}});
            } 
        }
        //cout << m << ' ' << l << ' ' << r << ' ' << can << endl;
        if (can) l = m ;
        else r = m;
    }
    cout << l << endl;

    return 0;
}

• Subtask 1: 100 / 100