oj.uz

Submission #535200

# Submission time Handle Problem Language Result Execution time Memory
535200 2022-03-09T16:46:55 Z rainboy 버스 (JOI14_bus) C
100 / 100
 475 ms 45772 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define M	300000
#define N_	(M * 2)

unsigned int X = 12345;

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

int *ej[N_], eo[N_], uu[N_], xx[N_];

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

		while (j < k) {
			int c = uu[ii[j]] != uu[i_] ? uu[ii[j]] - uu[i_] : xx[ii[j]] - xx[i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int xx_[N_];

void dfs(int i, int x) {
	int o;

	if (xx_[i] != -1)
		return;
	xx_[i] = x;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j, x);
	}
}

int main() {
	static int ii[N_];
	int n, n_, m, q, h, i;

	scanf("%d%d", &n, &m), n_ = m * 2;
	for (h = 0; h < m; h++)
		scanf("%d%d%d%d", &uu[h << 1 | 0], &uu[h << 1 | 1], &xx[h << 1 | 0], &xx[h << 1 | 1]), uu[h << 1 | 0]--, uu[h << 1 | 1]--;
	for (i = 0; i < n_; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n_; i++)
		ii[i] = i;
	sort(ii, 0, n_);
	for (i = 0; i + 1 < n_; i++)
		if (uu[ii[i]] == uu[ii[i + 1]]) {
			append(ii[i], ii[i + 1]);
			if (xx[ii[i]] == xx[ii[i + 1]])
				append(ii[i + 1], ii[i]);
		}
	for (h = 0; h < m; h++)
		append(h << 1 | 0, h << 1 | 1);
	i = 0;
	while (i < n_ && uu[ii[i]] == 0)
		i++;
	memset(xx_, -1, n_ * sizeof *xx_);
	while (i--)
		dfs(ii[i], xx[ii[i]]);
	scanf("%d", &q);
	while (q--) {
		int x, lower, upper;

		scanf("%d", &x);
		lower = -1, upper = n_;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if (uu[ii[i]] < n - 1 || xx[ii[i]] <= x)
				lower = i;
			else
				upper = i;
		}
		printf("%d\n", lower == -1 || uu[ii[lower]] != n - 1 ? -1 : xx_[ii[lower]]);
	}
	return 0;
}

Compilation message

bus.c: In function 'append':
bus.c:42:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
bus.c: In function 'main':
bus.c:66:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d%d", &n, &m), n_ = m * 2;
      |  ^~~~~~~~~~~~~~~~~~~~~
bus.c:68:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d%d%d", &uu[h << 1 | 0], &uu[h << 1 | 1], &xx[h << 1 | 0], &xx[h << 1 | 1]), uu[h << 1 | 0]--, uu[h << 1 | 1]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bus.c:88:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bus.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d", &x);
      |   ^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 28 ms 1912 KB Output is correct
3 Correct 29 ms 1944 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 536 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 24 ms 932 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 24 ms 1080 KB Output is correct
10 Correct 33 ms 2100 KB Output is correct
11 Correct 24 ms 1444 KB Output is correct
12 Correct 36 ms 2216 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 44116 KB Output is correct
2 Correct 334 ms 44212 KB Output is correct
3 Correct 355 ms 44072 KB Output is correct
4 Correct 321 ms 44072 KB Output is correct
5 Correct 335 ms 44216 KB Output is correct
6 Correct 343 ms 44116 KB Output is correct
7 Correct 381 ms 43636 KB Output is correct
8 Correct 353 ms 44424 KB Output is correct
9 Correct 345 ms 44256 KB Output is correct
10 Correct 434 ms 42888 KB Output is correct
11 Correct 475 ms 42924 KB Output is correct
12 Correct 439 ms 42996 KB Output is correct
13 Correct 439 ms 42876 KB Output is correct
14 Correct 418 ms 42924 KB Output is correct
15 Correct 440 ms 43052 KB Output is correct
16 Correct 106 ms 26924 KB Output is correct
17 Correct 118 ms 26876 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 45632 KB Output is correct
2 Correct 371 ms 45304 KB Output is correct
3 Correct 358 ms 45688 KB Output is correct
4 Correct 368 ms 45772 KB Output is correct
5 Correct 364 ms 45268 KB Output is correct
6 Correct 393 ms 45676 KB Output is correct
7 Correct 402 ms 45204 KB Output is correct
8 Correct 377 ms 45636 KB Output is correct
9 Correct 419 ms 45728 KB Output is correct
10 Correct 467 ms 44608 KB Output is correct
11 Correct 460 ms 44532 KB Output is correct
12 Correct 466 ms 44584 KB Output is correct
13 Correct 469 ms 44528 KB Output is correct
14 Correct 461 ms 44404 KB Output is correct
15 Correct 471 ms 44456 KB Output is correct
16 Correct 126 ms 27780 KB Output is correct