oj.uz

Submission #536319

# Submission time Handle Problem Language Result Execution time Memory
536319 2022-03-12T20:56:21 Z rainboy 물병 (JOI14_bottle) C
100 / 100
 749 ms 105292 KB 
#include <stdio.h>
#include <string.h>

#define N	2000
#define M	2000
#define N_	200000
#define M_	(N * M * 4)
#define INF	0x3f3f3f3f

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int uu[M_], vv[M_], ww[M_], m_;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (ww[hh[j]] == ww[h])
				j++;
			else if (ww[hh[j]] < ww[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N_], ww_[N_];

int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}

void join(int i, int j, int w) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, ww_[i] = w;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, ww_[j] = w;
	}
}

int query(int i, int j) {
	int w = 0;

	while (i != j && (ww_[i] != INF || ww_[j] != INF))
		if (ww_[i] < ww_[j])
			w = ww_[i], i = ds[i];
		else
			w = ww_[j], j = ds[j];
	return i != j ? -1 : w;
}

int main() {
	static char cc[N][M + 1];
	static int dd[N][M], uu_[N][M], qu[N * M], hh[M_];
	int n, n_, m, q, h, i, j, u, v, head, cnt;

	scanf("%d%d%d%d", &n, &m, &n_, &q);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			dd[i][j] = n * m, uu_[i][j] = -1;
	head = cnt = 0;
	for (u = 0; u < n_; u++) {
		scanf("%d%d", &i, &j), i--, j--;
		dd[i][j] = 0, uu_[i][j] = u, qu[head + cnt++] = i * m + j;
	}
	while (cnt) {
		int ij, d;

		ij = qu[cnt--, head++], i = ij / m, j = ij % m, d = dd[i][j] + 1, u = uu_[i][j];
		for (h = 0; h < 4; h++) {
			int i_ = i + di[h], j_ = j + dj[h];

			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == '.') {
				if (dd[i_][j_] > d)
					dd[i_][j_] = d, uu_[i_][j_] = u, qu[head + cnt++] = i_ * m + j_;
				else if ((v = uu_[i_][j_]) != u)
					uu[m_] = u, vv[m_] = v, ww[m_] = d + dd[i_][j_] - 1, m_++;
			}
		}
	}
	for (h = 0; h < m_; h++)
		hh[h] = h;
	sort(hh, 0, m_);
	memset(ds, -1, n_ * sizeof *ds);
	memset(ww_, 0x3f, n_ * sizeof *ww_);
	for (h = 0; h < m_; h++)
		join(uu[hh[h]], vv[hh[h]], ww[hh[h]]);
	while (q--) {
		scanf("%d%d", &i, &j), i--, j--;
		printf("%d\n", query(i, j));
	}
	return 0;
}

Compilation message

bottle.c: In function 'main':
bottle.c:76:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d%d%d", &n, &m, &n_, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~
bottle.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
bottle.c:110:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 3 ms 2516 KB Output is correct
3 Correct 4 ms 2864 KB Output is correct
4 Correct 60 ms 4804 KB Output is correct
5 Correct 65 ms 4800 KB Output is correct
6 Correct 59 ms 4760 KB Output is correct
7 Correct 64 ms 4752 KB Output is correct
8 Correct 70 ms 5028 KB Output is correct
9 Correct 61 ms 4940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22840 KB Output is correct
2 Correct 24 ms 6440 KB Output is correct
3 Correct 316 ms 47960 KB Output is correct
4 Correct 354 ms 53364 KB Output is correct
5 Correct 415 ms 58236 KB Output is correct
6 Correct 320 ms 47832 KB Output is correct
7 Correct 357 ms 53632 KB Output is correct
8 Correct 403 ms 58204 KB Output is correct
9 Correct 459 ms 65708 KB Output is correct
10 Correct 325 ms 51276 KB Output is correct
11 Correct 332 ms 52208 KB Output is correct
12 Correct 108 ms 51532 KB Output is correct
13 Correct 161 ms 48628 KB Output is correct
14 Correct 103 ms 51456 KB Output is correct
15 Correct 158 ms 48756 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22860 KB Output is correct
2 Correct 21 ms 5784 KB Output is correct
3 Correct 194 ms 46680 KB Output is correct
4 Correct 365 ms 53504 KB Output is correct
5 Correct 438 ms 58488 KB Output is correct
6 Correct 445 ms 65740 KB Output is correct
7 Correct 330 ms 51208 KB Output is correct
8 Correct 335 ms 53572 KB Output is correct
9 Correct 117 ms 51712 KB Output is correct
10 Correct 155 ms 48812 KB Output is correct
11 Correct 138 ms 47740 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 50928 KB Output is correct
2 Correct 568 ms 66976 KB Output is correct
3 Correct 308 ms 51292 KB Output is correct
4 Correct 602 ms 79480 KB Output is correct
5 Correct 749 ms 94672 KB Output is correct
6 Correct 428 ms 59640 KB Output is correct
7 Correct 289 ms 51048 KB Output is correct
8 Correct 88 ms 49156 KB Output is correct
9 Correct 558 ms 105292 KB Output is correct
10 Correct 423 ms 60236 KB Output is correct
11 Correct 542 ms 91896 KB Output is correct
12 Correct 436 ms 75788 KB Output is correct