oj.uz

Submission #705246

# Submission time Handle Problem Language Result Execution time Memory
705246 2023-03-03T17:03:15 Z rainboy Prize (CEOI22_prize) C
100 / 100
 1961 ms 237084 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 119788 KB Output is correct
2 Correct 858 ms 119836 KB Output is correct
3 Correct 848 ms 81724 KB Output is correct
4 Correct 815 ms 81616 KB Output is correct
5 Correct 849 ms 81704 KB Output is correct
6 Correct 800 ms 87804 KB Output is correct
7 Correct 793 ms 87752 KB Output is correct
8 Correct 758 ms 87968 KB Output is correct
9 Correct 771 ms 81776 KB Output is correct
10 Correct 811 ms 81588 KB Output is correct
11 Correct 783 ms 81596 KB Output is correct
12 Correct 794 ms 81684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 119796 KB Output is correct
2 Correct 761 ms 119656 KB Output is correct
3 Correct 831 ms 81612 KB Output is correct
4 Correct 860 ms 81868 KB Output is correct
5 Correct 859 ms 81632 KB Output is correct
6 Correct 809 ms 87752 KB Output is correct
7 Correct 858 ms 87880 KB Output is correct
8 Correct 891 ms 87808 KB Output is correct
9 Correct 886 ms 88096 KB Output is correct
10 Correct 901 ms 88192 KB Output is correct
11 Correct 811 ms 88016 KB Output is correct
12 Correct 970 ms 88124 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 112176 KB Output is correct
2 Correct 672 ms 112132 KB Output is correct
3 Correct 571 ms 74464 KB Output is correct
4 Correct 576 ms 74484 KB Output is correct
5 Correct 569 ms 74308 KB Output is correct
6 Correct 642 ms 80588 KB Output is correct
7 Correct 633 ms 80740 KB Output is correct
8 Correct 636 ms 80680 KB Output is correct
9 Correct 617 ms 80796 KB Output is correct
10 Correct 599 ms 81044 KB Output is correct
11 Correct 628 ms 80896 KB Output is correct
12 Correct 601 ms 81096 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1500 ms 227220 KB Output is correct
2 Correct 1495 ms 227580 KB Output is correct
3 Correct 1347 ms 152500 KB Output is correct
4 Correct 1333 ms 152532 KB Output is correct
5 Correct 1334 ms 152436 KB Output is correct
6 Correct 1498 ms 165184 KB Output is correct
7 Correct 1600 ms 164972 KB Output is correct
8 Correct 1436 ms 165076 KB Output is correct
9 Correct 1421 ms 165672 KB Output is correct
10 Correct 1438 ms 165560 KB Output is correct
11 Correct 1466 ms 165548 KB Output is correct
12 Correct 1661 ms 165604 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1961 ms 237084 KB Output is correct
2 Correct 1848 ms 236980 KB Output is correct
3 Correct 1823 ms 160740 KB Output is correct
4 Correct 1856 ms 160864 KB Output is correct
5 Correct 1710 ms 160696 KB Output is correct
6 Correct 1906 ms 173260 KB Output is correct
7 Correct 1759 ms 172920 KB Output is correct
8 Correct 1852 ms 173120 KB Output is correct
9 Correct 1806 ms 173628 KB Output is correct
10 Correct 1789 ms 173500 KB Output is correct
11 Correct 1772 ms 173556 KB Output is correct
12 Correct 1748 ms 173596 KB Output is correct