Submission #705246

#	Time	Username	Problem	Language	Result	Execution time	Memory
705246		rainboy	Prize (CEOI22_prize)	C11	100 / 100	1961 ms	237084 KiB

Main

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

#define N	1000000
#define Q	100000

unsigned int X = 12345;

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

int t;

int *ej[2][N], eo[2][N], dd[2][N], pp[2][N], qq[2][N], sz[2][N], ta[2][N], tb[2][N], rr[2];

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

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

int dfs1(int p, int i, int d) {
	int o, s, k_, j_;

	dd[t][i] = d, pp[t][i] = p;
	s = 1, k_ = 0, j_ = -1;
	for (o = eo[t][i]; o--; ) {
		int j = ej[t][i][o], k = dfs1(i, j, d + 1);

		s += k;
		if (k_ < k)
			k_ = k, j_ = j;
	}
	sz[t][i] = s, qq[t][i] = j_;
	return s;
}

int time;

void dfs2(int i, int q) {
	int o, j_;

	ta[t][i] = time++;
	j_ = qq[t][i], qq[t][i] = q;
	if (j_ != -1)
		dfs2(j_, q);
	for (o = eo[t][i]; o--; ) {
		int j = ej[t][i][o];

		if (j != j_)
			dfs2(j, j);
	}
	tb[t][i] = time;
}

int lca(int i, int j) {
	while (qq[t][i] != qq[t][j])
		if (dd[t][qq[t][i]] > dd[t][qq[t][j]])
			i = pp[t][qq[t][i]];
		else
			j = pp[t][qq[t][j]];
	return dd[t][i] < dd[t][j] ? i : j;
}

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)
			if (ta[1][ii[j]] == ta[1][i_])
				j++;
			else if (ta[1][ii[j]] < ta[1][i_]) {
				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;
	}
}

int ds[2][N]; long long xx[2][N];

int find(int i) {
	int p;

	if (ds[t][i] < 0)
		return i;
	p = ds[t][i];
	ds[t][i] = find(p);
	xx[t][i] += xx[t][p];
	return ds[t][i];
}

void join(int i, int j, long long x) {
	int ri = find(i), rj = find(j);

	x -= xx[t][i] - xx[t][j];
	i = ri, j = rj;
	if (i == j)
		return;
	if (ds[t][i] > ds[t][j])
		ds[t][i] = j, xx[t][i] = x;
	else {
		if (ds[t][i] == ds[t][j])
			ds[t][i]--;
		ds[t][j] = i, xx[t][j] = -x;
	}
}

int main() {
	static int ii[N];
	static long long ans[Q][2];
	int n, k, cnt, q, g, h, i, j, p, a;

	scanf("%d%d%*d%d", &n, &k, &q);
	for (t = 0; t < 2; t++) {
		for (i = 0; i < n; i++)
			ej[t][i] = (int *) malloc(2 * sizeof *ej[t][i]);
		for (i = 0; i < n; i++) {
			scanf("%d", &p), p--;
			if (p == -2)
				rr[t] = i;
			else
				append(p, i);
		}
		dfs1(-1, rr[t], 0);
		time = 0, dfs2(rr[t], rr[t]);
	}
	cnt = 0;
	for (i = 0; i < n; i++)
		if (ta[0][i] < k)
			ii[cnt++] = i;
	sort(ii, 0, k);
	for (h = 0; h < k; h++)
		printf("%d%c", ii[h] + 1, h + 1 < k ? ' ' : '\n');
	fflush(stdout);
	for (h = 0; h + 1 < k; h++)
		printf("? %d %d\n", ii[h] + 1, ii[h + 1] + 1), fflush(stdout);
	printf("!\n"), fflush(stdout);
	for (t = 0; t < 2; t++)
		memset(ds[t], -1, n * sizeof *ds[t]); 
	for (h = 0; h + 1 < k; h++) {
		i = ii[h], j = ii[h + 1];
		for (t = 0; t < 2; t++) {
			int di, dj;

			scanf("%d%d", &di, &dj);
			a = lca(i, j);
			join(i, a, di), join(j, a, dj);
		}
	}
	for (g = 0; g < q; g++) {
		scanf("%d%d", &i, &j), i--, j--;
		for (t = 0; t < 2; t++) {
			a = lca(i, j);
			find(i), find(j), find(a);
			ans[g][t] = xx[t][i] + xx[t][j] - xx[t][a] * 2;
		}
	}
	for (g = 0; g < q; g++)
		printf("%lld %lld\n", ans[g][0], ans[g][1]);
	fflush(stdout);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:122:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |  scanf("%d%d%*d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:127:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |    scanf("%d", &p), p--;
      |    ^~~~~~~~~~~~~~~
Main.c:154:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |    scanf("%d%d", &di, &dj);
      |    ^~~~~~~~~~~~~~~~~~~~~~~
Main.c:160:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24