Submission #948940

#	Time	Username	Problem	Language	Result	Execution time	Memory
948940		IBory	물병 (JOI14_bottle)	C++17	100 / 100	1126 ms	97712 KiB

bottle

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 4000007, LIM = 200007;
char C[MAX];
int pv[MAX], D[MAX], R[LIM], P[LIM];
pii LR[LIM], QS[LIM];

int Find(int n) {
	if (n == R[n]) return n;
	return R[n] = Find(R[n]);
}

void Union(int a, int b) {
	a = Find(a), b = Find(b);
	if (a == b) return;
	R[b] = a;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, K, T;
	cin >> N >> M >> K >> T;
	for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> C[i * M + j];
	for (int i = 1; i <= K; ++i) {
		int a, b;
		cin >> a >> b; a--; b--;
		P[i] = a * M + b;
	}

	vector<int> mv = {1, -1};
	mv.push_back(M); mv.push_back(-M);
	memset(D, 0x3f, sizeof(D));
	queue<int> Q;
	for (int i = 1; i <= K; ++i) {
		D[P[i]] = 0;
		pv[P[i]] = i;
		Q.push(P[i]);
	}

	vector<pair<int, pii>> E;
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		for (int k = 0; k < 4; ++k) {
			int next = cur + mv[k];
			if (k == 0 && next % M == 0) continue;
			if (k == 1 && cur % M == 0) continue;
			if (next < 0 || N * M <= next) continue;
			if (C[next] == '#') continue;

			if (D[next] > 1e9) {
				D[next] = D[cur] + 1;
				pv[next] = pv[cur];
				Q.push(next);
			}
			else if (pv[cur] != pv[next]) {
				E.emplace_back(D[cur] + D[next], pii{pv[cur], pv[next]});
			}
		}
	}

	// Does sorting necessary?
	sort(E.begin(), E.end()); 
	vector<pair<int, pii>> TE;
	iota(R, R + LIM, 0);
	for (auto [n, p] : E) {
		auto [a, b] = p;
		if (Find(a) != Find(b)) {
			TE.emplace_back(n, p);
			Union(a, b);
		}
	}
	swap(E, TE); TE.clear();
	E.emplace_back(1e9, pii{1, 1});

	for (int i = 1; i <= T; ++i) cin >> QS[i].first >> QS[i].second;
	fill(LR, LR + LIM, pii{-1, MAX});
	while (1) {
		vector<pii> cand;
		for (int i = 1; i <= T; ++i) {
			auto [l, r] = LR[i];
			if (l + 1 < r) cand.emplace_back((l + r) >> 1, i);
		}
		if (cand.empty()) break;
		sort(cand.begin(), cand.end());

		iota(R, R + LIM, 0);
		int aidx = 0, bidx = 0;
		while (aidx < E.size()) {
			while (bidx < cand.size() && cand[bidx].first < E[aidx].first) {
				auto [mid, id] = cand[bidx++];
				auto [a, b] = QS[id];
				(Find(a) == Find(b) ? LR[id].second : LR[id].first) = mid;
			}
			auto [c, d] = E[aidx++].second;
			Union(c, d);
		}
	}

	for (int i = 1; i <= T; ++i) {
		int ans = LR[i].second;
		if (ans == MAX) ans = -1;
		cout << ans << '\n';
	}
	return 0;
}

Compilation message (stderr)

bottle.cpp: In function 'int main()':
bottle.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   while (aidx < E.size()) {
      |          ~~~~~^~~~~~~~~~
bottle.cpp:91:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    while (bidx < cand.size() && cand[bidx].first < E[aidx].first) {
      |           ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30