Submission #527264

#	Time	Username	Problem	Language	Result	Execution time	Memory
527264		BhavayGoyal	Mecho (IOI09_mecho)	C++14	100 / 100	760 ms	16324 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];
vii d1(801, vi(801, inf)), d2(801, vi(801, inf));
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;}
 
void bfs1()
{
    queue<array<int, 2>> q;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (arr[i][j] == 'H')
            {
                d1[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 = x[0]+i, nj = x[1]+j;
            if (isValid(ni, nj) && arr[ni][nj] != 'T' && arr[ni][nj] != 'D' && d1[ni][nj] == inf)
            {
                d1[ni][nj] = d1[i][j]+1;
                q.push({ni, nj});
            }
        }
    }
}

bool isFiss(int mid)
{
    d2 = vii(801, vi(801, inf));
    queue<array<int, 2>> q;
    if (mid < d1[st[0]][st[1]]) {
        q.push(st);
        d2[st[0]][st[1]] = 0;
    }
    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] != 'T' && d2[ni][nj] == inf && ((mid+((d2[i][j]+1)/s)) < d1[ni][nj]))
            {
                d2[ni][nj] = d2[i][j]+1;
                q.push({ni, nj});
            }
        }
    }
    return d2[des[0]][des[1]] != inf;
}
 
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};
        }
    }
    bfs1();
 
    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: 100 / 100