Submission #1205247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205247		I_am_Polish_Girl	Maze (JOI23_ho_t3)	C++20	0 / 100	1 ms	584 KiB

Main

#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;


typedef long long ll;
typedef long double ld;

int log_ = 12;
int inf = 1000000007;

long long mod = 998244353;

int p = 499;

int NADIYA = 39;

int n, m;

vector <pair <int, int>> go = { {0 , 1} , {0 , -1} , {1 , 0} , {-1 , 0} };
vector <vector <int>> deep;

vector <vector <bool>> t;


bool checer(int i, int j) {
	if ((i < 0) or (j < 0))
		return false;

	if ((i >= n) or (j >= m))
		return false;

	return true;
}


queue<pair <int, int>> q1;
queue<pair <int, int>> q2;


vector <set <int>> vs_n;
vector <set <int>> vs_m;

void dfs(int i, int j) {

	vs_n[i].erase(j);
	vs_m[j].erase(i);


	for (int k = 0; k < 4; k++) {
		int i_ = i + go[k].first;
		int j_ = j + go[k].second;

		if (checer(i_, j_) == true) {
			if ((deep[i_][j_] == inf) and (t[i_][j_] == 0)) {
				deep[i_][j_] = deep[i][j];
				q1.push({ i_, j_ });

				dfs(i_, j_);
			}

			if ((deep[i_][j_] == inf) and (t[i_][j_] == 1)) {
				deep[i_][j_] = deep[i][j];
				
				vs_n[i_].erase(j_);
				vs_m[j_].erase(i_);

				q1.push({ i_, j_ });
			}
		}
	}
}


vector <vector <int>> t2;

int k;

void dfs2(int i, int j) {

	t2[i][j] = 1;

	for (int K = 0; K < 4; K++) {
		int i_ = i + go[K].first;
		int j_ = j + go[K].second;

		if (checer(i_, j_) == true) {
			if ((deep[i_][j_] == deep[i][j]) and (t2[i_][j_] == 0)) {
				dfs2(i_, j_);

				if (abs(j_ - j) == 1) {
					int P = (j_ - j) * k;

					int j__ = j_ + P;

					if ((j__ < m) and (j__ >= 0))
					{
						int mn_ = i_ - k + 1;
						int mx_ = i_ + k - 1;

						mn_ = max(mn_, 0);
						mx_ = min(mx_, n - 1);

						while (*vs_m[j__].lower_bound(mn_) <= mx_) {
							int i__ = *vs_m[j__].lower_bound(mn_);

							deep[i__][j__] = deep[i][j] + 1;
							q2.push({ i__, j__ });

							vs_m[j__].erase(i__);
							vs_n[i__].erase(j__);
						}
					}


					P /= k;
					P *= k - 1;

					int i2 = i_ - k;
					int j2 = j_ + P;

					if ((checer(i2, j2) == true) and (vs_n[i2].count(j2) > 0)) {
						vs_n[i2].erase(j2);
						vs_m[j2].erase(i2);


						deep[i2][j2] = deep[i][j] + 1;
						q2.push({ i2 , j2 });
					}


					i2 = i_ + k;
					j2 = j_ + P;

					if ((checer(i2, j2) == true) and (vs_n[i2].count(j2) > 0)) {
						vs_n[i2].erase(j2);
						vs_m[j2].erase(i2);

						deep[i2][j2] = deep[i][j] + 1;
						q2.push({ i2 , j2 });
					}
				}


				if (abs(i_ - i) == 1) {
					int P = (i_ - i) * k;

					int i__ = i_ + P;


					if ((i__ < n) and (i__ >= 0))
					{
						int mn_ = j_ - k + 1;
						int mx_ = j_ + k - 1;

						mn_ = max(mn_, 0);
						mx_ = min(mx_, m - 1);

						while (*vs_n[i__].lower_bound(mn_) <= mx_) {
							int j__ = *vs_n[i__].lower_bound(mn_);

							deep[i__][j__] = deep[i][j] + 1;
							q2.push({ i__, j__ });

							vs_m[j__].erase(i__);
							vs_n[i__].erase(j__);
						}
					}


					P /= k;
					P *= k - 1;

					int j2 = j_ - k;
					int i2 = i_ + P;

					if ((checer(i2, j2) == true) and (vs_n[i2].count(j2) > 0)) {
						vs_n[i2].erase(j2);
						vs_m[j2].erase(i2);


						deep[i2][j2] = deep[i][j] + 1;
						q2.push({ i2 , j2 });
					}



					j2 = j_ + k;
					i2 = i_ + P;

					if ((checer(i2, j2) == true) and (vs_n[i2].count(j2) > 0)) {
						vs_n[i2].erase(j2);
						vs_m[j2].erase(i2);

						deep[i2][j2] = deep[i][j] + 1;
						q2.push({ i2 , j2 });
					}
				}

			}
		}
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m >> k;

	int i_st, j_st;
	cin >> i_st >> j_st;

	i_st--;
	j_st--;


	int i_fi, j_fi;
	cin >> i_fi >> j_fi;

	i_fi--;
	j_fi--;

	t.resize(n);

	for (int i = 0; i < n; i++) {
		t[i].resize(m);


		string s;
		cin >> s;

		for (int j = 0; j < m; j++) {

			if (s[j] == '.')
				t[i][j] = 0;
			else
				t[i][j] = 1;
		}
	}

	vs_n.resize(n);
	vs_m.resize(m);


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			vs_n[i].insert(j);
			vs_m[j].insert(i);
		}
	}

	for (int i = 0; i < n; i++) {
		vs_n[i].insert(-1);
		vs_n[i].insert(m);
	}

	for (int j = 0; j < m; j++) {
		vs_m[j].insert(-1);
		vs_m[j].insert(n);
	}

	deep.resize(n);

	for (int i = 0; i < n; i++) {
		deep[i].resize(m, inf);
	}

	deep[i_st][j_st] = 0;

	vs_n[i_st].erase(j_st);
	vs_m[j_st].erase(i_st);

	q1.push({ i_st , j_st });

	t2.resize(n);
	for (int i = 0; i < n; i++)
	{
		t2[i].resize(m);
	}

	for (int d = 0; d < n * m; d++) {

		int d__ = inf;
		int i_ = -1;
		int j_ = -1;

		while (q1.size() > 0) {
			int i = q1.front().first;
			int j = q1.front().second;

			vs_n[i].erase(j);
			vs_m[j].erase(i);
			q1.pop();

			if (d__ > abs(i - i_fi) + abs(j - j_fi)) {
				d__ = abs(i - i_fi) + abs(j - j_fi);

				i_ = i;
				j_ = j;
			}

			if (t[i][j] == 0)
				dfs(i, j);

			int i_ = i;
			int j_ = j;

			for (int pl = -k; pl <= k; pl++) {
				int i__ = i_ + pl;
				int mn_ = j_ - k;
				int mx_ = j_ + k;

				if (abs(pl) == k) {
					mn_++;
					mx_--;
				}

				mn_ = max(mn_, 0);
				mx_ = min(mx_, m - 1);


				if ((i__ < 0) or (i__ >= n))
					continue;

				while (*vs_n[i__].lower_bound(mn_) <= mx_) {
					int j__ = *vs_n[i__].lower_bound(mn_);

					vs_n[i__].erase(j__);
					vs_m[j__].erase(i__);


					deep[i__][j__] = deep[i_][j_] + 1;
					q2.push({ i__ , j__ });
				}
			}
		}




		//dfs2(i_, j_);


		swap(q1, q2);
	}

	cout << deep[i_fi][j_fi];
}

/*
5 5 2
2 2
4 4
#....
#.##.
####.
##...
.....


4 4 1
1 1
4 4
.#..
###.
.##.
..#.
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6