oj.uz

Submission #32156

# Submission time Handle Problem Language Result Execution time Memory
32156 2017-09-28T03:14:23 Z minimario Palindromes (APIO14_palindrome) C++14
100 / 100
 126 ms 67116 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 300005;
 
struct node {
	int len;
	int next[26];
	int suff;
	int ct;
};
 
node t[MAX];
int i = 0;
int ans = 0;
 
void roots() {
	t[0].len = -1; t[0].suff = 0;
	t[1].len = 0; t[1].suff = 0;
}
 
int ct = 2;
int maxsuff = 1;
string s;
void add(int pos) {
	int j = maxsuff;
	int c = s[pos] - 'a'; // the character
	while (s[pos-t[j].len-1] != s[pos]) {
		j = t[j].suff;
	}
	if (t[j].next[c] == 0) {
		t[j].next[c] = ct;
		t[ct].len = t[j].len + 2;
		ct++;
	}
	maxsuff = t[j].next[c];
	if (j == 0) {
		t[maxsuff].suff = 1;
	}
	else {
		j = t[j].suff;
		while (s[pos-t[j].len-1] != s[pos]) {
			j = t[j].suff; 
		}
		if (t[j].next[c] == 0) {
			t[j].next[c] = ct;
			t[ct].len = t[j].len + 2;
			ct++;
		}
		t[maxsuff].suff = t[j].next[c];
	}
	t[maxsuff].ct++;
}
 
bool v[MAX];
 
vector<int> g[MAX];
void create() {
	for (int i=2; i<MAX; i++) {
		if (t[i].suff > 1) {
			g[t[i].suff].push_back(i);
		}
	}
}
void dfs(int u) {
	v[u] = true;
	for (int i : g[u]) {
		dfs(i);
		t[u].ct += t[i].ct;
	}
}
 
int main() {
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> s;
	s = " " + s;
	roots();
	for (int i=1; i<s.length(); i++) {
		add(i);
	}
	v[0] = v[1] = true;
	create();
	for (int i=2; i<MAX; i++) {
		if (!v[i]) { dfs(i); }
	}
	long long maxi = 0;
	for (int i=2; i<MAX; i++) {
		maxi = max(maxi, (long long)t[i].len * (long long)t[i].ct);
	}
	cout << maxi << endl;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<s.length(); i++) {
                 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 43484 KB Output is correct
2 Correct 6 ms 43484 KB Output is correct
3 Correct 0 ms 43484 KB Output is correct
4 Correct 3 ms 43484 KB Output is correct
5 Correct 6 ms 43484 KB Output is correct
6 Correct 6 ms 43484 KB Output is correct
7 Correct 3 ms 43484 KB Output is correct
8 Correct 3 ms 43484 KB Output is correct
9 Correct 3 ms 43484 KB Output is correct
10 Correct 6 ms 43484 KB Output is correct
11 Correct 3 ms 43484 KB Output is correct
12 Correct 6 ms 43484 KB Output is correct
13 Correct 9 ms 43484 KB Output is correct
14 Correct 3 ms 43484 KB Output is correct
15 Correct 6 ms 43484 KB Output is correct
16 Correct 6 ms 43484 KB Output is correct
17 Correct 6 ms 43484 KB Output is correct
18 Correct 3 ms 43484 KB Output is correct
19 Correct 6 ms 43484 KB Output is correct
20 Correct 9 ms 43484 KB Output is correct
21 Correct 6 ms 43484 KB Output is correct
22 Correct 3 ms 43484 KB Output is correct
23 Correct 3 ms 43484 KB Output is correct
24 Correct 3 ms 43484 KB Output is correct
25 Correct 6 ms 43484 KB Output is correct
26 Correct 3 ms 43484 KB Output is correct
27 Correct 3 ms 43484 KB Output is correct
28 Correct 0 ms 43484 KB Output is correct
29 Correct 6 ms 43484 KB Output is correct
30 Correct 6 ms 43484 KB Output is correct
31 Correct 0 ms 43484 KB Output is correct
32 Correct 6 ms 43484 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 43484 KB Output is correct
2 Correct 6 ms 43484 KB Output is correct
3 Correct 6 ms 43484 KB Output is correct
4 Correct 6 ms 43484 KB Output is correct
5 Correct 6 ms 43484 KB Output is correct
6 Correct 6 ms 43484 KB Output is correct
7 Correct 13 ms 43484 KB Output is correct
8 Correct 3 ms 43484 KB Output is correct
9 Correct 3 ms 43484 KB Output is correct
10 Correct 6 ms 43484 KB Output is correct
11 Correct 3 ms 43484 KB Output is correct
12 Correct 6 ms 43484 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43856 KB Output is correct
2 Correct 0 ms 43788 KB Output is correct
3 Correct 3 ms 44088 KB Output is correct
4 Correct 6 ms 44020 KB Output is correct
5 Correct 6 ms 43616 KB Output is correct
6 Correct 6 ms 43616 KB Output is correct
7 Correct 3 ms 43748 KB Output is correct
8 Correct 6 ms 43484 KB Output is correct
9 Correct 9 ms 43484 KB Output is correct
10 Correct 6 ms 43484 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48864 KB Output is correct
2 Correct 19 ms 47844 KB Output is correct
3 Correct 13 ms 51212 KB Output is correct
4 Correct 16 ms 49508 KB Output is correct
5 Correct 26 ms 44668 KB Output is correct
6 Correct 23 ms 45392 KB Output is correct
7 Correct 16 ms 46452 KB Output is correct
8 Correct 9 ms 43636 KB Output is correct
9 Correct 6 ms 45196 KB Output is correct
10 Correct 13 ms 44536 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 60092 KB Output is correct
2 Correct 63 ms 55044 KB Output is correct
3 Correct 46 ms 67116 KB Output is correct
4 Correct 46 ms 58156 KB Output is correct
5 Correct 126 ms 48168 KB Output is correct
6 Correct 49 ms 53816 KB Output is correct
7 Correct 33 ms 52184 KB Output is correct
8 Correct 6 ms 44324 KB Output is correct
9 Correct 9 ms 44324 KB Output is correct
10 Correct 119 ms 47244 KB Output is correct
11 Correct 86 ms 55400 KB Output is correct
12 Correct 9 ms 45756 KB Output is correct