oj.uz

Submission #205620

# Submission time Handle Problem Language Result Execution time Memory
205620 2020-02-29T10:26:34 Z mihai50000 Palindromes (APIO14_palindrome) C++17
15 / 100
 58 ms 44816 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct PalTree
{
	struct Node
	{
		map <char, int> urm;
		int len;
		int cnt;
		int fail;
	};
	
	int n = 2;
	int ans = 0;
	
	vector <Node> vec;
	
	PalTree(string s) : vec(s.size() + 2)
	{
		vec[0].fail = vec[0].len = -1;
		vec[1].fail = vec[1].len = 0;
		
		int last = 0;
		
		for(int i = 0; i < s.size(); ++i)
		{
			char ch = s[i];
			int pos = last;
			
			while(s[i - vec[pos].len - 1] != ch)
			{
				pos = vec[pos].fail;
			}
			if(vec[pos].urm.count(ch))
			{
				pos = vec[pos].urm[ch];
				vec[pos].cnt++;
				last = pos;
				continue;
			}
			
			vec[n].cnt = 1;
			vec[n].len = vec[pos].len + 2;
			vec[pos].urm[ch] = n;
			
			int fail = vec[pos].fail;
			
			while(fail != -1 && !(s[i - 1 - vec[fail].len] == ch && vec[fail].urm.count(ch)))
			{
				fail = vec[fail].fail;
			}
			if(vec[fail].urm.count(ch))
				fail = vec[fail].urm[ch];
			
			if(fail < 1)
				fail = 1;
			
			vec[n].fail = fail;
			last = n;
			n++;
		}
		
		for(int i = n - 1; i > 0; --i)
		{
			vec[vec[i].fail].cnt += vec[i].cnt;
			ans = max(ans, vec[i].cnt * vec[i].len);
		}
	}
};

main()
{
	string s;
	cin >> s;
	
	PalTree arb(s);
	cout << arb.ans << '\n';
}

Compilation message

palindrome.cpp: In constructor 'PalTree::PalTree(std::__cxx11::string)':
palindrome.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size(); ++i)
                  ~~^~~~~~~~~~
palindrome.cpp: At global scope:
palindrome.cpp:75:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2040 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 23 ms 15352 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 58 ms 44816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -