Submission #762718

#	Time	Username	Problem	Language	Result	Execution time	Memory
762718		rainboy	Through Another Maze Darkly (CCO21_day1problem3)	C11	25 / 25	998 ms	224772 KiB

Main

#include <stdio.h>
#include <stdlib.h>

#define N	800000
#define N2	((N - 1) * 2)
#define N_	(1 << 21)	/* N_ = pow2(ceil(log2(N2))) */
#define Q	800000

unsigned int X = 12345;

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

int *ej[N], eo[N], *ei[N], eo_[N], ii[N2], dd[N2], n2;

void dfs(int p, int i, int d) {
	int o, o_;

	if (p == -1)
		for (o = 0; o < eo[i]; o++) {
			int j = ej[i][o];

			eo_[d] += 2;
			ii[n2] = j, dd[n2] = d, n2++;
			dfs(i, j, d);
			ii[n2] = i, dd[n2] = d, n2++;
		}
	else {
		for (o = 0; o < eo[i]; o++) {
			int j = ej[i][o];

			if (j == p)
				break;
		}
		for (o_ = o + 1; o_ < eo[i]; o_++) {
			int j = ej[i][o_];

			eo_[d + 1] += 2;
			ii[n2] = j, dd[n2] = d + 1, n2++;
			dfs(i, j, d + 1);
			ii[n2] = i, dd[n2] = d + 1, n2++;
		}
		for (o_ = 0; o_ < o; o_++) {
			int j = ej[i][o_];

			eo_[d] += 2;
			ii[n2] = j, dd[n2] = d, n2++;
			dfs(i, j, d);
			ii[n2] = i, dd[n2] = d, n2++;
		}
	}
}

long long tt[Q];

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 (tt[hh[j]] == tt[h])
				j++;
			else if (tt[hh[j]] < tt[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 st[N_ * 2], n_;

void update(int i) {
	for (i += n_; i > 0; i >>= 1)
		st[i]++;
}

int query(int k) {
	int i = 1;

	while (i < n_)
		if (k < st[i << 1 | 0])
			i = i << 1 | 0;
		else
			k -= st[i << 1 | 0], i = i << 1 | 1;
	return i - n_;
}

int main() {
	static int hh[Q], ans[Q];
	int n, q, h, h_, i, j, k, d, o;
	long long t;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++) {
		scanf("%d", &eo[i]);
		ej[i] = (int *) malloc(eo[i] * sizeof *ej[i]);
		for (o = 0; o < eo[i]; o++) {
			scanf("%d", &j), j--;
			ej[i][(o - 1 + eo[i]) % eo[i]] = j;
		}
	}
	dfs(-1, 0, 0);
	for (d = 0; d < n; d++)
		ei[d] = (int *) malloc(eo_[d] * sizeof *ei[d]), eo_[d] = 0;
	for (i = 0; i < n2; i++) {
		d = dd[i];
		ei[d][eo_[d]++] = i;
	}
	for (h = 0; h < q; h++)
		scanf("%lld", &tt[h]), tt[h]--;
	for (h = 0; h < q; h++)
		hh[h] = h;
	sort(hh, 0, q);
	n_ = 1;
	while (n_ < n2)
		n_ <<= 1;
	t = 0, k = 0;
	for (h = 0, d = 0; h < q; h++) {
		h_ = hh[h];
		while (tt[h_] - t >= k)
			if (d < n) {
				for (o = 0; o < eo_[d]; o++) {
					i = ei[d][o];
					update(i);
				}
				t += k, k += eo_[d];
				d++;
			} else
				t = t + (tt[h_] - t) / k * k;
		ans[h_] = ii[query(tt[h_] - t)];
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h] + 1);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:101:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d", &eo[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:104:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |    scanf("%d", &j), j--;
      |    ^~~~~~~~~~~~~~~
Main.c:116:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   scanf("%lld", &tt[h]), tt[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 12 / 12
• Subtask 4: 5 / 5