Submission #527211

#	Time	Username	Problem	Language	Result	Execution time	Memory
527211		BhavayGoyal	Mecho (IOI09_mecho)	C++14	58 / 100	1101 ms	11960 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define vii vector<vector<int>>
#define vi vector<int>
#define v vector
#define pii pair<int, int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#define si set<int>
#define usi unordered_set<int>
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
#define pb push_back
#define MOD 1000000007
int inf = 1e9;

char arr[801][801];
int beesTime[801][801], mechotime[801][801];
int n, s;
array<int, 2> st, des;

vii temp = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool isValid(int i, int j) {return i >= 1 && j >= 1 && i <= n && j <= n;}

bool isFiss(int mid)
{
    queue<array<int, 2>> q;
    memset(beesTime, -1, sizeof beesTime);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (arr[i][j] == 'H') {
                beesTime[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    while (!q.empty())
    {
        int i = q.front()[0], j = q.front()[1];
        q.pop();
        for (auto x : temp)
        {
            int ni = i+x[0], nj = j+x[1];
            if (!isValid(ni, nj) || arr[ni][nj] == 'D' || arr[ni][nj] == 'T' || arr[ni][nj] == 'H' || beesTime[ni][nj] != -1) continue;
            beesTime[ni][nj] = beesTime[i][j]+1;
            q.push({ni, nj});
        }
    }
    beesTime[des[0]][des[1]] = inf;

    q.push(st);
    memset(mechotime, -1, sizeof mechotime);
    mechotime[st[0]][st[1]] = 0;
    if (beesTime[st[0]][st[1]] <= mid) q.pop();
    while (!q.empty())
    {
        int i = q.front()[0], j = q.front()[1];
        q.pop();
        if (i == des[0] && j == des[1]) return true;
        for (auto x : temp)
        {
            int ni = i+x[0], nj = j+x[1];
            if (!isValid(ni, nj) || arr[ni][nj] == 'H' || arr[ni][nj] == 'T' || mechotime[ni][nj] != -1) continue;
            if (beesTime[ni][nj] <= ((mechotime[i][j]+1)/s)+mid) continue;
            mechotime[ni][nj] = mechotime[i][j]+1;
            q.push({ni, nj});
        }
    }
    return false;
}

void sol()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= n; j++) 
        {
            cin >> arr[i][j];
            if (arr[i][j] == 'M') st = {i, j};
            if (arr[i][j] == 'D') des = {i, j};
        }
    }

    int i = 0, j = n*n;
    int ans = -1;
    while (i <= j)
    {
        int mid = (i+j)/2;
        if (isFiss(mid)) {
            ans = mid;
            i = mid+1;
        }
        else j = mid-1;
    }
    cout << ans;
}

signed main(){
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        sol();
    // cerr << "Finished" << endl;
}

• Subtask 1: 58 / 100