Submission #395753

#	Time	Username	Problem	Language	Result	Execution time	Memory
395753		rainboy	Savez (COCI15_savez)	C11	120 / 120	103 ms	44584 KiB

savez

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

#define N	2000000
#define N_	(N + 2)
#define A	26
#define MD	0x7fffffff

int max(int a, int b) { return a > b ? a : b; }

int *ek[N], *ev[N], eo[N], X;

void init() {
	X = 12345;
}

int hash(int k) {
	return (long long) k * X % MD % N;
}

int get(int k) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k)
			return ev[h][o];
	return 0;
}

void put(int k, int v) {
	int h = hash(k), o = eo[h]++;

	if (o == 0) {
		ek[h] = (int *) malloc(sizeof *ek[h]);
		ev[h] = (int *) malloc(sizeof *ev[h]);
	} else if (o >= 2 && (o & o - 1) == 0) {
		ek[h] = (int *) realloc(ek[h], o * 2 * sizeof *ek[h]);
		ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
	}
	ek[h][o] = k, ev[h][o] = v;
}

int zz[N];

void zzz(char *cc, int n) {
	int i, l, r;

	zz[0] = n;
	for (i = 1, l = 0, r = 0; i < n; i++)
		if (i + zz[i - l] < r)
			zz[i] = zz[i - l];
		else {
			l = i, r = max(r, l);
			while (r < n && cc[r] == cc[r - l])
				r++;
			zz[i] = r - l;
		}
}

int main() {
	static int dp[N_];
	int n, n_, ans;

	init();
	scanf("%d", &n);
	n_ = 2, ans = 0;
	while (n--) {
		static char cc[N + 1];
		int l, h, t, x;

		scanf("%s", cc), l = strlen(cc);
		zzz(cc, l);
		t = 1, x = 0;
		for (h = 0; h < l; h++) {
			int a = cc[h] - 'A', t_;

			t_ = get(t * A + a);
			if (t_ == 0)
				put(t * A + a, t_ = n_++);
			t = t_;
			if (zz[l - 1 - h] == h + 1)
				x = max(x, dp[t]);
		}
		ans = max(ans, dp[t] = max(dp[t], x + 1));
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

savez.c: In function 'put':
savez.c:37:30: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   37 |  } else if (o >= 2 && (o & o - 1) == 0) {
      |                            ~~^~~
savez.c: In function 'main':
savez.c:66:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
savez.c:72:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%s", cc), l = strlen(cc);
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12