oj.uz

Submission #948940

# Submission time Handle Problem Language Result Execution time Memory
948940 2024-03-18T16:47:20 Z IBory 물병 (JOI14_bottle) C++17
100 / 100
 1126 ms 97712 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23132 KB Output is correct
2 Correct 9 ms 23224 KB Output is correct
3 Correct 8 ms 23048 KB Output is correct
4 Correct 282 ms 28276 KB Output is correct
5 Correct 273 ms 28508 KB Output is correct
6 Correct 271 ms 28280 KB Output is correct
7 Correct 320 ms 28260 KB Output is correct
8 Correct 284 ms 28368 KB Output is correct
9 Correct 276 ms 28264 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25672 KB Output is correct
2 Correct 26 ms 26360 KB Output is correct
3 Correct 193 ms 44804 KB Output is correct
4 Correct 278 ms 46848 KB Output is correct
5 Correct 309 ms 50428 KB Output is correct
6 Correct 179 ms 44796 KB Output is correct
7 Correct 275 ms 47192 KB Output is correct
8 Correct 309 ms 49916 KB Output is correct
9 Correct 344 ms 56340 KB Output is correct
10 Correct 187 ms 45064 KB Output is correct
11 Correct 235 ms 47216 KB Output is correct
12 Correct 98 ms 46844 KB Output is correct
13 Correct 115 ms 44620 KB Output is correct
14 Correct 89 ms 46840 KB Output is correct
15 Correct 94 ms 44764 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25704 KB Output is correct
2 Correct 23 ms 26224 KB Output is correct
3 Correct 147 ms 44620 KB Output is correct
4 Correct 291 ms 47096 KB Output is correct
5 Correct 339 ms 51400 KB Output is correct
6 Correct 345 ms 55528 KB Output is correct
7 Correct 192 ms 45164 KB Output is correct
8 Correct 282 ms 47304 KB Output is correct
9 Correct 115 ms 47336 KB Output is correct
10 Correct 113 ms 45020 KB Output is correct
11 Correct 109 ms 44956 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 51104 KB Output is correct
2 Correct 791 ms 67412 KB Output is correct
3 Correct 187 ms 45056 KB Output is correct
4 Correct 865 ms 75496 KB Output is correct
5 Correct 1126 ms 97504 KB Output is correct
6 Correct 596 ms 56880 KB Output is correct
7 Correct 195 ms 45052 KB Output is correct
8 Correct 76 ms 45044 KB Output is correct
9 Correct 998 ms 97712 KB Output is correct
10 Correct 594 ms 61684 KB Output is correct
11 Correct 810 ms 96744 KB Output is correct
12 Correct 667 ms 73188 KB Output is correct