oj.uz

Submission #33800

# Submission time Handle Problem Language Result Execution time Memory
33800 2017-11-02T02:35:06 Z sinhriv Palindromes (APIO14_palindrome) C++14
100 / 100
 23 ms 67764 KB 
#include <bits/stdc++.h>

using namespace std;

struct eerTree{
	static const int Alpabet = 30;
	static const int N = 5e5;

	struct Node{
		int nxt[Alpabet];
		int suffix;
		int len;
		int value;
	};


	int cnt;
	int current;
	Node tree[N];
	string source;

	void addLetter(int pos){
		int u = current;
		int c = source[pos] - 'a';



		while(true){
			int len = tree[u].len;
			if(pos - len - 1 >= 0 && source[pos - len - 1] == source[pos]){
				break;
			}
			u = tree[u].suffix;
		}
		
		if(tree[u].nxt[c] != 0){
			++tree[tree[u].nxt[c]].value;
			current = tree[u].nxt[c];
			return;
		}

		tree[u].nxt[c] = ++cnt;
		tree[cnt].value = 1;
		tree[cnt].len = tree[u].len + 2;


		if(tree[cnt].len == 1){
			tree[cnt].suffix = 2;
			current = cnt;
			return;
		}

		while(true){
			u = tree[u].suffix;
			int len = tree[u].len;
			if(pos - len - 1 >= 0 && source[pos - len - 1] == source[pos]){
				tree[cnt].suffix = tree[u].nxt[c];
				break;
			}
		}
		current = cnt;
	}

	void Init(string x){
		cnt = current = 2; 
		source = x;

		tree[1].len = -1;
		tree[1].suffix = 1;
		tree[2].len = 0;
		tree[2].suffix = 1;
	
		for(int i = 0; i < source.size(); ++i){
			addLetter(i);
		}
	}

	long long calc(){
		long long ans = 0;
		for(int i = cnt; i >= 1; --i){
			ans = max(ans, 1LL * tree[i].value * tree[i].len);
			tree[tree[i].suffix].value += tree[i].value;
		}
		return ans;
	}
}f;


int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 

	string s;
	cin >> s;


	f.Init(s);

	cout << f.calc();

	return 0;
}

Compilation message

palindrome.cpp: In member function 'void eerTree::Init(std::__cxx11::string)':
palindrome.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < source.size(); ++i){
                    ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:91:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 66628 KB Output is correct
2 Correct 0 ms 66628 KB Output is correct
3 Correct 0 ms 66628 KB Output is correct
4 Correct 0 ms 66628 KB Output is correct
5 Correct 0 ms 66628 KB Output is correct
6 Correct 0 ms 66628 KB Output is correct
7 Correct 0 ms 66628 KB Output is correct
8 Correct 0 ms 66628 KB Output is correct
9 Correct 0 ms 66628 KB Output is correct
10 Correct 0 ms 66628 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 67004 KB Output is correct
2 Correct 3 ms 67004 KB Output is correct
3 Correct 6 ms 67004 KB Output is correct
4 Correct 6 ms 67004 KB Output is correct
5 Correct 0 ms 67004 KB Output is correct
6 Correct 3 ms 67004 KB Output is correct
7 Correct 0 ms 67004 KB Output is correct
8 Correct 0 ms 67004 KB Output is correct
9 Correct 3 ms 67004 KB Output is correct
10 Correct 3 ms 67004 KB Output is correct

Subtask #5
27.0 / 27.0

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