oj.uz

Submission #395752

# Submission time Handle Problem Language Result Execution time Memory
395752 2021-04-28T20:31:29 Z rainboy Savez (COCI15_savez) C
0 / 120
 70 ms 65540 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() {
	int h;

	X = 12345;
	for (h = 0; h < N; h++) {
		ek[h] = (int *) malloc(2 * sizeof *ek[h]);
		ev[h] = (int *) malloc(2 * sizeof *ev[h]);
	}
}

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 >= 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:40:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   40 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
savez.c: In function 'main':
savez.c:69:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
savez.c:75:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf("%s", cc), l = strlen(cc);
      |   ^~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -