Submission #587318

#	Time	Username	Problem	Language	Result	Execution time	Memory
587318		rainboy	Palindromi (COCI22_palindromi)	C11	110 / 110	92 ms	32168 KiB

Main

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

#define N	100000
#define LN	17	/* LN = ceil(log2(N)) */
#define N_	(N * (LN + 4))

int len[N_], tt[N_][2], ff[N_], fff[N_][2];

int node(int l) {
	static int _ = 1;

	len[_] = l;
	return _++;
}

int ds[N], ans[N], *aa[N], head[N], cnt[N], cnt_[N], ss0[N], ss1[N], pp[N], qq[N];

void append(int i, int a) {
	int s;

	if (cnt[i] == cnt_[i]) {
		int *bb = (int *) malloc((cnt_[i] *= 2) * sizeof *bb), h;

		for (h = 0; h < cnt[i]; h++)
			bb[h] = aa[i][(head[i] + h) % cnt[i]];
		free(aa[i]);
		aa[i] = bb, head[i] = 0;
	}
	aa[i][(head[i] + cnt[i]++) % cnt_[i]] = a;
	s = qq[i];
	if (len[s] == cnt[i] - 1 || aa[i][(head[i] + cnt[i] - 2 - len[s]) % cnt_[i]] != a)
		s = fff[s][a];
	if (!tt[s][a]) {
		int u = node(len[s] + 2), f = len[u] == 1 ? ss0[i] : tt[fff[s][a]][a];

		ff[u] = f;
		memcpy(fff[u], fff[f], sizeof fff[f]), fff[u][aa[i][(head[i] + cnt[i] - 1 - len[f]) % cnt_[i]]] = f;
		tt[s][a] = u;
		ans[i]++;
	}
	s = tt[s][a];
	qq[i] = s;
	if (len[s] == cnt[i])
		pp[i] = s;
}

void prepend(int i, int a) {
	int s;

	if (cnt[i] == cnt_[i]) {
		int *bb = (int *) malloc((cnt_[i] *= 2) * sizeof *bb), h;

		for (h = 0; h < cnt[i]; h++)
			bb[h] = aa[i][(head[i] + h) % cnt[i]];
		free(aa[i]);
		aa[i] = bb, head[i] = 0;
	}
	head[i] = (head[i] - 1 + cnt_[i]) % cnt_[i], cnt[i]++, aa[i][head[i]] = a;
	s = pp[i];
	if (len[s] == cnt[i] - 1 || aa[i][(head[i] + 1 + len[s]) % cnt_[i]] != a)
		s = fff[s][a];
	if (!tt[s][a]) {
		int u = node(len[s] + 2), f = len[u] == 1 ? ss0[i] : tt[fff[s][a]][a];

		ff[u] = f;
		memcpy(fff[u], fff[f], sizeof fff[f]), fff[u][aa[i][(head[i] + len[f]) % cnt_[i]]] = f;
		tt[s][a] = u;
		ans[i]++;
	}
	s = tt[s][a];
	pp[i] = s;
	if (len[s] == cnt[i])
		qq[i] = s;
}

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	int h;

	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (cnt[i] > cnt[j]) {
		ds[j] = i;
		for (h = 0; h < cnt[j]; h++)
			append(i, aa[j][(head[j] + h) % cnt_[j]]);
		free(aa[j]);
	} else {
		ds[i] = j;
		for (h = cnt[i] - 1; h >= 0; h--)
			prepend(j, aa[i][(head[i] + h) % cnt_[i]]);
		free(aa[i]);
	}
}

int main() {
	static char cc[N + 1];
	int n, h, i, j;

	scanf("%d%s", &n, cc);
	for (i = 0; i < n; i++) {
		aa[i] = (int *) malloc((cnt_[i] = 2) * sizeof *aa[i]);
		head[i] = 0;
		ss0[i] = node(0), ss1[i] = node(-1);
		ff[ss0[i]] = ss1[i];
		fff[ss0[i]][0] = fff[ss0[i]][1] = ss1[i], fff[ss1[i]][0] = fff[ss1[i]][1] = ss1[i];
		pp[i] = qq[i] = ss0[i];
		append(i, cc[i] - '0');
	}
	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		join(i, j);
		printf("%d\n", ans[find(i)]);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:106:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:118:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50