Submission #393882

#	Time	Username	Problem	Language	Result	Execution time	Memory
393882		MaisyDoge13	Mecho (IOI09_mecho)	C++17	84 / 100	254 ms	16416 KiB

mecho

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <array>
#include <set>
#include <climits>
#include <map>
#include <memory>
#include <string>
#include <deque>
using namespace std;

#define input "mecho.in"
#define output "mecho.out"
#define int long long
int n, s;
int ans=-1; //will be maxed during the binary search
vector<vector<int>> bees_reach;
deque<pair<int, int>> bees_bfs; //r, c start off while taking input
vector<string> a;//input field
vector<vector<int>> reach_copy;
deque<pair<int, int>> bfs_copy;
vector<pair<int, int>> dirs = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};
bool check(int m) {
    vector<vector<int>> mecho_reach = reach_copy;
    deque<pair<int, int>> mecho_bfs = bfs_copy;

    //do bfs with mecho's location except mech can never go to a tile with bees there less than or equal to (m*s)+steps
    while (!mecho_bfs.empty()) {
        pair<int, int> curr=mecho_bfs.front();
        mecho_bfs.pop_front();
        int r=curr.first, c=curr.second;
        int curr_steps=mecho_reach[r][c];
        //cout << "r " << r << " c " << c << " curr_steps " <<  curr_steps << endl;
        if (a[r][c]=='D') {
            return 1;
        }
        for (pair<int, int> dir: dirs) {
            int new_r=r+dir.first, new_c=c+dir.second;
            if (new_r<0 || new_r>=n || new_c<0 || new_c>=n || a[new_r][new_c]=='T' || mecho_reach[new_r][new_c]!=-1) continue;
            if (bees_reach[new_r][new_c]<=(m*s)+curr_steps+1 && bees_reach[new_r][new_c]!=-1) continue;
            mecho_reach[new_r][new_c]=curr_steps+1;
            mecho_bfs.push_back({new_r, new_c});
        }
    }


    return 0;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen(input, "r", stdin);
    //freopen(output, "w", stdout);
    cin >> n >> s;
    bees_reach.resize(n, vector<int>(n, -1));
    reach_copy.resize(n, vector<int>(n, -1));
    a.reserve(n);
    for (int r=0;r<n;r++) {
        string s; cin >> s;
        a.push_back(s);
        for (int c=0;c<n;c++) {
            if (a[r][c]=='H') {
                bees_bfs.push_back({r, c});
                bees_reach[r][c]=0;
            }
            else if (a[r][c]=='M') {
                bfs_copy.push_back({r, c});
                reach_copy[r][c]=0;
            }
        }   
    }
    while (!bees_bfs.empty()) {
        pair<int, int> curr=bees_bfs.front();
        bees_bfs.pop_front();
        int r=curr.first, c=curr.second; int curr_steps=bees_reach[r][c];
        for (pair<int, int> dir: dirs) {
            int new_r=r+dir.first, new_c=c+dir.second;
            if (new_r<0 || new_r>=n || new_c<0 || new_c>=n || a[new_r][new_c]=='T' || a[new_r][new_c]=='D') continue;
            if (bees_reach[new_r][new_c]==-1) {
                bees_reach[new_r][new_c]=curr_steps+s;
                bees_bfs.push_back({new_r, new_c});
            }
        }
    }
    int l=0, r=1000*1000;
    while (l<=r) {
        int m=(l+r)/2;
        //cout << m << endl;
        if (check(m)) {
            ans=m;
            l=m+1;
        }
        else {
            r=m-1;
        }
    }
    cout << ans << endl;
}

• Subtask 1: 84 / 100