oj.uz

Submission #395753

# Submission time Handle Problem Language Result Execution time Memory
395753 2021-04-28T20:33:40 Z rainboy Savez (COCI15_savez) C
120 / 120
 103 ms 44584 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 7 ms 12844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 43 ms 44584 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18884 KB Output is correct
2 Correct 87 ms 36804 KB Output is correct
3 Correct 81 ms 19172 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39116 KB Output is correct
2 Correct 86 ms 39712 KB Output is correct
3 Correct 91 ms 38468 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 30528 KB Output is correct
2 Correct 47 ms 30120 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 29144 KB Output is correct
2 Correct 47 ms 29580 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 28972 KB Output is correct
2 Correct 45 ms 28928 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 28604 KB Output is correct
2 Correct 52 ms 38732 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1832 KB Output is correct
2 Correct 43 ms 1784 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1764 KB Output is correct
2 Correct 56 ms 2012 KB Output is correct
3 Correct 103 ms 2260 KB Output is correct