Submission #1286780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286780		samarthkulkarni	Mecho (IOI09_mecho)	C++20	16 / 100	1098 ms	42496 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize("fast-math")

#define ll long long
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first 
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};

void solution();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

pr operator+(pr p1, pr p2) {
	pr ans = {p1.ff +p2.ff, p1.ss+p2.ss};
	return ans;
}


const int MAXN = 805;
char A[MAXN][MAXN];
ll n, s;
pr start, destination;
vector<pr> H;
bool vis1[MAXN][MAXN], vis2[MAXN][MAXN];


bool correct(pr cords) {
	return cords.ff <= n && cords.ff >= 1 && 
		cords.ss <= n && cords.ss >= 1 &&
		A[cords.ff][cords.ss] != 'T';
}


bool isValid(ll T) {
	set<pr> bad(all(H));
	pr wa = {-1, -1};

	queue<pr> q1, q2;

	for (auto M : H) q2.push(M);
	q2.push(wa);
	ll k = 0;
	while (!q2.empty()) {
		pr e = q2.front(); q2.pop();
		if (e == wa) {
			if (q2.size() > 0) q2.push(wa);
			if (k >= T) break;
			k++;
			continue;
		}


		if (vis2[e.ff][e.ss]) continue;
		vis2[e.ff][e.ss] = true;

		bad.insert(e);

		for (auto D : move4) {
			pr new_cords = e + D;
			if (!correct(new_cords) || vis2[new_cords.ff][new_cords.ss]) continue;
			q2.push(new_cords);
		}
	}

	q1.push(start);
	q1.push(wa);
	k = 0;
	while (!q1.empty()) {
		pr e = q1.front(); q1.pop();

		if (e == wa) {

			// if time is up
			if (k >= s) {

				while (!q2.empty()) {
					pr m = q2.front(); q2.pop();
					if (m == wa) {
						if (q2.size() > 0) q2.push(wa);
						break;
					}

					if (vis2[m.ff][m.ss]) continue;
					vis2[m.ff][m.ss] = true;

					bad.insert(m);
					for (auto D : move4) {
						pr nkw = m + D;
						if (!correct(nkw) || vis2[nkw.ff][nkw.ss]) continue;
						q2.push(nkw);
					}
				}
				k = 0;

			}

			k++;
			if (q1.size() > 0) q1.push(wa);
		}

		if (bad.count(e) || vis1[e.ff][e.ss]) continue;
		vis1[e.ff][e.ss] = true;

		if (e == destination) return true;

		for (auto D : move4) {
			pr nkw = e + D;
			if (!correct(nkw) || vis1[nkw.ff][nkw.ss]) continue;
			q1.push(nkw);
		}

	}

	return false;
}


void solution() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) {
    		cin >> A[i][j];
    		if (A[i][j] == 'M') start = {i, j};
    		if (A[i][j] == 'D') destination = {i, j};
    		if (A[i][j] == 'H') H.push_back({i, j});
    	}
    }


    
    ll p = 0, q = 1e3;
    ll ans = -1;
    while (p <= q) {
    	ll mid = (p + q)/2;
    	if (isValid(mid)) {
    		ans = mid;
    		p = mid+1;
    	}else q = mid-1;

    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++) {
    			vis1[i][j] = vis2[i][j] = 0;
    		}
    	}
    }


    cout << ans << endl;


}

• Subtask 1: 16 / 100