제출 #1047518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047518		Nonoze	Mecho (IOI09_mecho)	C++17	100 / 100	845 ms	47188 KiB

mecho

/*
*	Author: Nonoze
*	Created: Wednesday 07/08/2024
*/
#include <bits/stdc++.h>
using namespace std;

#ifndef _IN_LOCAL
	#define dbg(...)
#endif

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x, bool write=0, bool write2=1, bool nothing=1) { if (write && write2) cout << x << endl; else if (write) cout << x << ' '; else cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p, bool write=0, bool nothing=1, bool write2=1) { read(p.first, write, 0), read(p.second, write, 0); if (write && write2) cout << endl;}
template<typename T> void read(vector<T>& v, bool write=0) { for (auto& x : v) read(x, write, 0, 1); if (write) cout << endl; }
template<typename T1, typename T2> void read(T1& x, T2& y, bool write=0) { read(x, write), read(y, write); if (write) cout << endl; }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z, bool write=0) { read(x, write), read(y, write), read(z, write); if (write) cout << endl; }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz, bool write=0) { read(x, write), read(y, write), read(z, write), read(zz, write); if (write) cout << endl; }
template<typename T> void print(T x) { read(x, 1); }
template<typename T1, typename T2> void print(T1 x, T2 y) { read(x, y, 1); }
template<typename T1, typename T2, typename T3> void print(T1 x, T2 y, T3 z) { read(x, y, z, 1); }
template<typename T1, typename T2, typename T3, typename T4> void print(T1 x, T2 y, T3 z, T4 zz) { read(x, y, z, zz, 1); }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

#define int long long
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, k, s, t;
vector<int> h;
vector<vector<int>> adj;

bool ok(int wait) {
	vector<bool> bees(n, 0), visited(n, 0); visited[s]=1;
	for (auto u: h) bees[u]=1;
	queue<pair<int, pair<int, int>>> qbees;
	queue<pair<int, pair<int, int>>> q2; q2.push({s, {0, 0}});
	for (auto u: h) qbees.push({u, {0, 0}});
	while (!q2.empty()) {
		bool bee=1;
		if (qbees.empty() || qbees.front().se.se>=q2.front().se.se) bee=0, swap(qbees, q2);
		int u=qbees.front().fi, nb=qbees.front().se.fi, time=qbees.front().se.se; qbees.pop();
		if (!bee) swap(qbees, q2);
		if (!bee && time<wait) {
			if (!bees[u]) q2.push({u, {0, time+1}});
			continue;
		}
		if (bees[u] && !bee) continue;
		for (auto v: adj[u]) {
			if (bees[v] || (!bee && visited[v])) continue;
			if (bee && t==v) continue;
			if (bee) bees[v]=1;
			else visited[v]=1;
			if (!bee && v==t) return 1;
			if (!bee) {
				if (nb+1>=k) q2.push({v, {0, time+1}});
				else q2.push({v, {nb+1, time}});
			} else qbees.push({v, {0, time+1}});
		}
	}
	return 0;
}


void solve() {
	read(n, k);
	vector<string> a(n); read(a);
	adj.clear(), adj.resize(n*n);
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (a[i][j]=='T') continue;
			int act=i*n+j;
			if (i && a[i-1][j]!='T') {
				int nxt=(i-1)*n+j;
				adj[act].pb(nxt), adj[nxt].pb(act);
			}
			if (j && a[i][j-1]!='T') {
				int nxt=i*n+j-1;
				adj[act].pb(nxt), adj[nxt].pb(act);
			}
			if (a[i][j]=='M') s=act;
			if (a[i][j]=='D') t=act;
			if (a[i][j]=='H') h.pb(act);
		}
	}
	n*=n;
	int ans=-1, l=0, r=n;
	while (l<=r) {
		int mid=(l+r)/2;
		if (ok(mid)) ans=mid, l=mid+1;
		else r=mid-1;
	}
	cout << ans << endl;
}

• Subtask 1: 100 / 100