oj.uz

Submission #32154

# Submission time Handle Problem Language Result Execution time Memory
32154 2017-09-28T03:13:14 Z minimario Palindromes (APIO14_palindrome) C++14
0 / 100
 26 ms 53184 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 43484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 43484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 43748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 46648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 53184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -