Submission #1205451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205451		I_am_Polish_Girl	Maze (JOI23_ho_t3)	C++20	94 / 100	2024 ms	571236 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;


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

vector <vector <bool>> t;

struct DSU
{
	int n, m;

	vector <int> link;
	vector <int> w;
	vector <int> answer;

	int T = 0;

	int find(int ind)
	{
		if (link[ind] == ind)
			return ind;
		link[ind] = find(link[ind]);

		return link[ind];
	}

	pair <int , int> lower_bound(int i, int j)
	{
		int i_ = i * m + j;

		int ans = answer[find(i_)];

		return { ans / m , ans % m };
	}

	void erase(int i, int j)
	{
		int i_ = i;
		int j_ = j;
		if (T == 0)
		{
			i_++;
		}
		else
		{
			j_++;
		}

		int i1 = i * m + j;
		int i2 = i_ * m + j_;

		i1 = find(i1);
		i2 = find(i2);

		int r = answer[i2];

		if (w[i1] < w[i2])
			swap(i1, i2);

		link[i2] = i1;
		w[i1] += w[i2];

		answer[i1] = r;
	}


	void init(int N , int M , int t)
	{
		T = t;
		
		n = N + 1;
		m = M+1;

		link.resize(n * m);
		answer.resize(n * m);
		w.resize(n * m, 1);

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				link[i * m + j] = i * m + j;
				answer[i * m + j] = i * m + j;
			}
		}


		link.resize(n * m);
	}
};


int n, m;

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;


DSU vs_n;
DSU vs_m;

void dfs(int i, int j) {

	vs_n.erase(i , j);
	vs_m.erase(i , j);


	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_);
				continue;
			}
		}
	}
}


vector <vector <int>> t2;

int k;

void dfs2(int i, int j , int x) {

	t2[i][j]++;

	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_] == x) and (t2[i_][j_] == 0)) or ((deep[i_][j_] == x - 1) and (t2[i_][j_] == 1))) {
				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.lower_bound( mn_ , j__).first <= mx_) {
							int i__ = vs_m.lower_bound(mn_, j__).first;

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


							vs_m.erase(i__, j__);
							//vs_m[j__].erase(i__);
							vs_n.erase(i__, j__);
							//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.lower_bound(i2 , j2 ) == make_pair(i2 , j2))) {
					
						vs_m.erase(i2, j2);
						vs_n.erase(i2, j2);

						//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.lower_bound(i2, j2) == make_pair(i2, j2))) {

						vs_m.erase(i2, j2);
						vs_n.erase(i2, j2);

						//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.lower_bound(i__ , mn_).second <= mx_) {
							int j__ = vs_n.lower_bound(i__, mn_).second;

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


							vs_m.erase(i__, j__);
							//vs_m[j__].erase(i__);
							vs_n.erase(i__, j__);
							//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.lower_bound(i2, j2) == make_pair(i2, j2))) {
						vs_m.erase(i2, j2);
						vs_n.erase(i2, j2);


						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.lower_bound(i2, j2) == make_pair(i2, j2))) {
						vs_m.erase(i2, j2);
						vs_n.erase(i2, j2);

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

				dfs2(i_, j_ , x);
			}
		}
	}
}

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);
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;


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

	vs_n.init(n, m , 1);
	vs_m.init(n, m , 0);


	

	deep.resize(n);

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

	deep[i_st][j_st] = 0;

	vs_n.erase(i_st , j_st);
	vs_m.erase(i_st, j_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;

			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;
			}
			dfs(i, j);
			
		}



		if (i_ != -1)
		{
			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.lower_bound(i__ , mn_).second <= mx_) {
					int j__ = vs_n.lower_bound(i__, mn_).second;

					vs_n.erase(i__, j__);
					vs_m.erase(i__, j__);
					

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


			dfs2(i_, j_ , d);
		}


		int ans = inf;

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

			if (checer(i, j))
			{
				ans = min(ans, deep[i][j]);
			}
		}

		if (ans != inf)
			break;


		swap(q1, q2);
	}

	int ans = inf;

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

		if (checer(i, j))
		{
			ans = min(ans, deep[i][j]);
		}
	}

	cout << min(ans ,deep[i_fi][j_fi]);
}

/*
6 6 1
1 6
2 3
..#.#.
##.###
####.#
...###
##.##.
.#.##.
*/

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