oj.uz

Submission #926878

# Submission time Handle Problem Language Result Execution time Memory
926878 2024-02-14T02:50:54 Z IBory 물병 (JOI14_bottle) C++17
60 / 100
 1768 ms 113124 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 4000007, LIM = 200007;
char C[MAX];
int R[MAX], pv[MAX], D[MAX], 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));
	iota(R, R + MAX, 0);
	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()); 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{0, 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:80: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]
   80 |   while (aidx < E.size()) {
      |          ~~~~~^~~~~~~~~~
bottle.cpp:81: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]
   81 |    while (bidx < cand.size() && cand[bidx].first < E[aidx].first) {
      |           ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 37468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37996 KB Output is correct
2 Correct 44 ms 40696 KB Output is correct
3 Correct 198 ms 59688 KB Output is correct
4 Correct 350 ms 61956 KB Output is correct
5 Correct 355 ms 64768 KB Output is correct
6 Correct 194 ms 59744 KB Output is correct
7 Correct 317 ms 61704 KB Output is correct
8 Correct 411 ms 65024 KB Output is correct
9 Correct 431 ms 70144 KB Output is correct
10 Correct 197 ms 60168 KB Output is correct
11 Correct 253 ms 60888 KB Output is correct
12 Correct 135 ms 61904 KB Output is correct
13 Correct 102 ms 59560 KB Output is correct
14 Correct 123 ms 61692 KB Output is correct
15 Correct 103 ms 59644 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37992 KB Output is correct
2 Correct 30 ms 40256 KB Output is correct
3 Correct 153 ms 59684 KB Output is correct
4 Correct 318 ms 62320 KB Output is correct
5 Correct 386 ms 64940 KB Output is correct
6 Correct 422 ms 70648 KB Output is correct
7 Correct 192 ms 60256 KB Output is correct
8 Correct 310 ms 62420 KB Output is correct
9 Correct 162 ms 62208 KB Output is correct
10 Correct 112 ms 59868 KB Output is correct
11 Correct 99 ms 59572 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 65636 KB Output is correct
2 Correct 992 ms 79148 KB Output is correct
3 Correct 195 ms 60008 KB Output is correct
4 Correct 1270 ms 86712 KB Output is correct
5 Correct 1768 ms 113124 KB Output is correct
6 Incorrect 643 ms 70948 KB Output isn't correct
7 Halted 0 ms 0 KB -