oj.uz

답안 #705235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705235 2023-03-03T16:35:06 Z rainboy Prize (CEOI22_prize) C
0 / 100
 1540 ms 227684 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1000000

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 p, int i, int q) {
	int o, j_;

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

		if (j != p && j != j_)
			dfs2(i, 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], 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, int x) {
	int ri = find(i), rj = find(j);

	x -= xx[t][i] - xx[t][j];
	if (ri == rj)
		return;
	i = ri, j = rj;
	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];
	int n, k, cnt, q, 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(-1, 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 ", ii[h] + 1);
	printf("\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);
		}
	}
	while (q--) {
		scanf("%d%d", &i, &j), i--, j--;
		for (t = 0; t < 2; t++) {
			a = lca(i, j);
			find(i), find(j), find(a);
			printf("%d ", xx[t][i] + xx[t][j] - xx[t][a] * 2);
		}
		printf("\n"), fflush(stdout);
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 686 ms 114264 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 750 ms 114256 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 582 ms 111308 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1416 ms 224408 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1540 ms 227684 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -