Submission #535200

#	Time	Username	Problem	Language	Result	Execution time	Memory
535200		rainboy	버스 (JOI14_bus)	C11	100 / 100	475 ms	45772 KiB

bus

#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 (stderr)

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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50