Submission #991214

#	Time	Username	Problem	Language	Result	Execution time	Memory
991214		model_code	Road Service 2 (JOI24_ho_t5)	C++17	100 / 100	933 ms	297300 KiB

Main

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

// ==================================================================================================================================================== その他の関数
// 位置 pos から x 手で移動できる最大位置
int GetMaxPosition(int pos, int x, vector<vector<int>>& par) {
	if (x == -1) return -50000;
	vector<int> dp0(23, -1);
	vector<int> dp1(23, -1);
	dp0[22] = pos;
	for (int i = 21; i >= 0; i--) {
		if ((x / (1 << i)) % 2 == 0) {
			dp0[i] = dp0[i + 1];
			dp1[i] = dp1[i + 1];
			continue;
		}
		if (dp0[i + 1] != -1) dp0[i] = max(dp0[i], par[3 * i + 1][dp0[i + 1]]);
		if (dp1[i + 1] != -1) dp0[i] = max(dp0[i], par[3 * i + 0][dp1[i + 1]]);
		if (dp0[i + 1] != -1) dp1[i] = max(dp1[i], par[3 * i + 2][dp0[i + 1]]);
		if (dp1[i + 1] != -1) dp1[i] = max(dp1[i], par[3 * i + 1][dp1[i + 1]]);
	}
	return dp0[0];
}

// 位置 pos から位置 goal 以上まで行くための最小コスト
int GetMinCost(int pos, int goal, vector<vector<int>>& par) {
	if (pos == -1) return 1000000000;
	if (pos >= goal) return 0;
	int cur1 = pos;
	int cur2 = -1;
	int ans = 0;
	for (int i = 21; i >= 0; i--) {
		int v1 = -1;
		int v2 = -1;
		if (cur1 != -1) v1 = max(v1, par[3 * i + 1][cur1]);
		if (cur2 != -1) v1 = max(v1, par[3 * i + 0][cur2]);
		if (cur1 != -1) v2 = max(v2, par[3 * i + 2][cur1]);
		if (cur2 != -1) v2 = max(v2, par[3 * i + 1][cur2]);
		if (v1 < goal && v2 < goal) {
			cur1 = v1;
			cur2 = v2;
			ans += (1 << i);
		}
	}
	if (cur1 != -1 && par[1][cur1] >= goal) return ans + 1;
	if (cur2 != -1 && par[1][cur2] >= goal) return ans + 2;
	if (cur1 != -1 && par[2][cur1] >= goal) return ans + 2;
	return ans + 3;
}

// 極小な区間だけを取り出す関数
vector<pair<int, int>> OnlyMinimal(vector<pair<int, int>> Ranges) {
	for (int i = 0; i < Ranges.size(); i++) Ranges[i].first *= -1;
	sort(Ranges.begin(), Ranges.end());
	vector<pair<int, int>> Return;
	int MinValue = (1 << 30);
	for (int i = 0; i < Ranges.size(); i++) {
		if (MinValue > Ranges[i].second) {
			MinValue = Ranges[i].second;
			Return.push_back(Ranges[i]);
		}
	}
	for (int i = 0; i < Return.size(); i++) Return[i].first *= -1;
	sort(Return.begin(), Return.end());
	return Return;
}

// 位置 pos を区間 [cl, cr] に修正
pair<int, int> FixPosition(int moto, int pos, int cl, int cr, int cost, vector<int>& C, vector<int>& NextCost1, vector<int>& NextCost2, vector<vector<int>>& par, vector<int>& UpLim) {
	if (pos < cl) return make_pair(-1, 1000000000);
	if (pos <= cr) return make_pair(pos, cost);
	if (C[pos] == 1) {
		int idx1 = NextCost1[cr];
		int idx2 = NextCost2[cr];
		int result = -1;
		if (idx1 >= cl) result = max(result, idx1);
		if (cost >= 2) {
			int prepos = GetMaxPosition(moto, cost - 2, par);
			int nexpos = UpLim[prepos];
			if (nexpos >= cl && NextCost2[min(cr, nexpos)] >= cl) result = max(result, NextCost2[min(cr, nexpos)]);
		}
		if (result != -1) return make_pair(result, cost);
		return make_pair(idx2, cost + 1);
	}
	return make_pair(NextCost2[cr], cost);
}

// 位置 pos から区間 [cl, cr] に行くための最小コスト
int RangeCost(int pos, int cl, int cr, vector<int>& C, vector<int>& NextCost1, vector<int>& NextCost2, vector<vector<int>>& par, vector<int>& UpLim) {
	int base = GetMinCost(pos, cl, par);
	int newpos = GetMaxPosition(pos, base, par);
	pair<int, int> fixpos = FixPosition(pos, newpos, cl, cr, base, C, NextCost1, NextCost2, par, UpLim);
	return fixpos.second;
}

// ==================================================================================================================================================== 問題を解く関数
vector<int> solve_subtask8(int H, int W, int Q, vector<vector<char>> A, vector<vector<char>> B, vector<int> C, vector<vector<pair<int, int>>> Query) {
	// Step 1. 連結成分を探す
	vector<vector<int>> GroupID(H, vector<int>(W, -1));
	int GroupCnt = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (GroupID[i][j] != -1) continue;
			queue<pair<int, int>> Que;
			Que.push(make_pair(i, j));
			GroupID[i][j] = GroupCnt;
			while (!Que.empty()) {
				int px = Que.front().first;
				int py = Que.front().second;
				Que.pop();
				if (px - 1 >= 0 && B[px - 1][py] == '1' && GroupID[px - 1][py] == -1) {
					GroupID[px - 1][py] = GroupCnt;
					Que.push(make_pair(px - 1, py));
				}
				if (px + 1 < H && B[px][py] == '1' && GroupID[px + 1][py] == -1) {
					GroupID[px + 1][py] = GroupCnt;
					Que.push(make_pair(px + 1, py));
				}
				if (py - 1 >= 0 && A[px][py - 1] == '1' && GroupID[px][py - 1] == -1) {
					GroupID[px][py - 1] = GroupCnt;
					Que.push(make_pair(px, py - 1));
				}
				if (py + 1 < W && A[px][py] == '1' && GroupID[px][py + 1] == -1) {
					GroupID[px][py + 1] = GroupCnt;
					Que.push(make_pair(px, py + 1));
				}
			}
			GroupCnt += 1;
		}
	}

	// Step 2. 各連結成分に対応する区間を求める
	vector<pair<int, int>> Range(GroupCnt, make_pair(100000000, -100000000));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			Range[GroupID[i][j]].first = min(Range[GroupID[i][j]].first, i);
			Range[GroupID[i][j]].second = max(Range[GroupID[i][j]].second, i);
		}
	}

	// Step 3. 各地点の直前のコスト 1, 2 の位置を計算
	vector<int> NextCost1(H, -1);
	vector<int> NextCost2(H, -1);
	for (int i = 0; i < H; i++) {
		if (i >= 1) {
			NextCost1[i] = NextCost1[i - 1];
			NextCost2[i] = NextCost2[i - 1];
		}
		if (C[i] == 1) NextCost1[i] = i;
		if (C[i] == 2) NextCost2[i] = i;
	}

	// Step 4. 最大値を計算
	vector<int> UpLim(H, -1);
	for (int i = 0; i < H; i++) UpLim[i] = i;
	for (pair<int, int> idx : Range) {
		UpLim[idx.first] = max(UpLim[idx.first], idx.second);
	}
	for (int i = 1; i < H; i++) UpLim[i] = max(UpLim[i], UpLim[i - 1]);

	// Step 5. ダブリングの初期化
	// par[3*d+e][i] ã¯é ‚ç‚¹ i からコスト 2^d+(e-1) でどこまで行けるか
	vector<vector<int>> par(66, vector<int>(H, -1));
	for (int i = 0; i < H; i++) par[0][i] = i;
	for (int i = 0; i < H; i++) par[1][i] = max(i, NextCost1[UpLim[i]]);
	for (int i = 0; i < H; i++) {
		int v1 = NextCost2[UpLim[i]];
		int v2 = NextCost1[UpLim[i]];
		int v3 = (v2 == -1 ? -1 : NextCost1[UpLim[v2]]);
		par[2][i] = max({ i, v1, v3 });
	}

	// Step 6. ダブリングの計算
	for (int d = 3; d < 66; d += 3) {
		for (int i = 0; i < H; i++) {
			par[d + 0][i] = max({ par[d - 3][par[d - 2][i]], par[d - 2][par[d - 3][i]] });
			par[d + 1][i] = max({ par[d - 3][par[d - 1][i]], par[d - 2][par[d - 2][i]], par[d - 1][par[d - 3][i]] });
			par[d + 2][i] = max({ par[d - 2][par[d - 1][i]], par[d - 1][par[d - 2][i]] });
		}
	}

	// Step 7. 各クエリにおける答えを計算
	vector<int> Answer(Q, -1);
	for (int t = 0; t < Q; t++) {
		vector<int> Groups;
		for (pair<int, int> idx : Query[t]) Groups.push_back(GroupID[idx.first][idx.second]);
		sort(Groups.begin(), Groups.end());
		Groups.erase(unique(Groups.begin(), Groups.end()), Groups.end());
		if (Groups.size() == 1) {
			Answer[t] = 0;
		}
		else {
			vector<pair<int, int>> List;
			for (int idx : Groups) List.push_back(Range[idx]);
			vector<pair<int, int>> Important = OnlyMinimal(List);
			vector<int> dpval(Important.size(), 1000000000);
			vector<int> dp0(Important.size(), -1);
			vector<int> dp1(Important.size(), -1);

			// 初期値の計算
			if (NextCost1[Important[0].second] < Important[0].first) {
				dpval[0] = 2;
				dp0[0] = NextCost2[Important[0].second];
				dp1[0] = -1;
			}
			else {
				dpval[0] = 1;
				dp0[0] = NextCost1[Important[0].second]; if (dp0[0] < Important[0].first) dp0[0] = -1;
				dp1[0] = NextCost2[Important[0].second]; if (dp1[0] < Important[0].first) dp1[0] = -1;
			}

			// 動的計画法
			for (int i = 1; i < Important.size(); i++) {
				int cl = Important[i].first;
				int cr = Important[i].second;
				int cost1 = 1000000000; if (dp0[i - 1] != -1) cost1 = RangeCost(dp0[i - 1], cl, cr, C, NextCost1, NextCost2, par, UpLim);
				int cost2 = 1000000000; if (dp1[i - 1] != -1) cost2 = RangeCost(dp1[i - 1], cl, cr, C, NextCost1, NextCost2, par, UpLim);
				dpval[i] = min({ dpval[i], dpval[i - 1] + cost1, dpval[i - 1] + cost2 + 1 });
				if (dpval[i] > 2 * H) break;
				int pos1 = GetMaxPosition(dp0[i - 1], dpval[i] - (dpval[i - 1] + 0) + 0, par);
				int pos2 = GetMaxPosition(dp1[i - 1], dpval[i] - (dpval[i - 1] + 1) + 0, par);
				int pos3 = GetMaxPosition(dp0[i - 1], dpval[i] - (dpval[i - 1] + 0) + 1, par);
				int pos4 = GetMaxPosition(dp1[i - 1], dpval[i] - (dpval[i - 1] + 1) + 1, par);
				pair<int, int> fix1 = FixPosition(dp0[i - 1], pos1, cl, cr, dpval[i] - (dpval[i - 1] + 0) + 0, C, NextCost1, NextCost2, par, UpLim);
				pair<int, int> fix2 = FixPosition(dp1[i - 1], pos2, cl, cr, dpval[i] - (dpval[i - 1] + 1) + 0, C, NextCost1, NextCost2, par, UpLim);
				pair<int, int> fix3 = FixPosition(dp0[i - 1], pos3, cl, cr, dpval[i] - (dpval[i - 1] + 0) + 1, C, NextCost1, NextCost2, par, UpLim);
				pair<int, int> fix4 = FixPosition(dp1[i - 1], pos4, cl, cr, dpval[i] - (dpval[i - 1] + 1) + 1, C, NextCost1, NextCost2, par, UpLim);
				if (fix1.second + (dpval[i - 1] + 0) == dpval[i] + 0) dp0[i] = max(dp0[i], fix1.first);
				if (fix1.second + (dpval[i - 1] + 0) == dpval[i] + 1) dp1[i] = max(dp1[i], fix1.first);
				if (fix2.second + (dpval[i - 1] + 1) == dpval[i] + 0) dp0[i] = max(dp0[i], fix2.first);
				if (fix2.second + (dpval[i - 1] + 1) == dpval[i] + 1) dp1[i] = max(dp1[i], fix2.first);
				if (fix3.second + (dpval[i - 1] + 0) == dpval[i] + 0) dp0[i] = max(dp0[i], fix3.first);
				if (fix3.second + (dpval[i - 1] + 0) == dpval[i] + 1) dp1[i] = max(dp1[i], fix3.first);
				if (fix4.second + (dpval[i - 1] + 1) == dpval[i] + 0) dp0[i] = max(dp0[i], fix4.first);
				if (fix4.second + (dpval[i - 1] + 1) == dpval[i] + 1) dp1[i] = max(dp1[i], fix4.first);
			}
			Answer[t] = dpval[Important.size() - 1];
			if (Answer[t] > 2 * H) Answer[t] = -1;
		}
	}

	// Step 8. 答えを返す
	return Answer;
}

// ==================================================================================================================================================== 入出力
int main() {
	// 入力
	int H, W, Q;
	scanf("%d%d%d", &H, &W, &Q);
	vector<vector<char>> A(H, vector<char>(W - 1, 0));
	vector<vector<char>> B(H - 1, vector<char>(W, 0));
	vector<vector<pair<int, int>>> Query(Q, vector<pair<int, int>>(0, make_pair(0, 0)));
	vector<int> C(H, 0);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) cin >> A[i][j];
	}
	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W; j++) cin >> B[i][j];
	}
	for (int i = 0; i < H; i++) cin >> C[i];
	for (int i = 0; i < Q; i++) {
		int t, x, y; scanf("%d", &t);
		for (int j = 0; j < t; j++) {
			scanf("%d%d", &x, &y); x--; y--;
			Query[i].push_back(make_pair(x, y));
		}
	}

	// 出力
	vector<int> Answer = solve_subtask8(H, W, Q, A, B, C, Query);
	for (int i = 0; i < Q; i++) printf("%d\n", Answer[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp:6: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    6 | #pragma warning (disable: 4996)
      | 
Main.cpp: In function 'std::vector<std::pair<int, int> > OnlyMinimal(std::vector<std::pair<int, int> >)':
Main.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < Ranges.size(); i++) Ranges[i].first *= -1;
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < Ranges.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < Return.size(); i++) Return[i].first *= -1;
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'std::vector<int> solve_subtask8(int, int, int, std::vector<std::vector<char> >, std::vector<std::vector<char> >, std::vector<int>, std::vector<std::vector<std::pair<int, int> > >)':
Main.cpp:217:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |    for (int i = 1; i < Important.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:254:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  254 |  scanf("%d%d%d", &H, &W, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:267:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |   int t, x, y; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~
Main.cpp:269:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |    scanf("%d%d", &x, &y); x--; y--;
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 6 / 6
• Subtask 6: 12 / 12
• Subtask 7: 26 / 26
• Subtask 8: 14 / 14