Submission #1119853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119853		raczek	Palindromes (APIO14_palindrome)	C++17	73 / 100	117 ms	131072 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
struct palTrie
{
	struct node
	{
		node* sons[30];
		vector<node*> edg;
		node* sufLink = nullptr;
		int val = 0;
		int sz = -1;
		node(node* suf, int s){
			sufLink = suf, sz = s;
			for(int i=0;i<30;i++) sons[i] = nullptr;
		}
		node(){
			for(int i=0;i<30;i++) sons[i] = nullptr;
		} 
	};
	string s;
	node Oroot;
	node* add(char let, int pos, node* prev)
	{
		debug(let);
		debug(pos);
		node* nw = nullptr;
		bool e = 0;
		while(prev != nullptr)
		{
			if(pos-1-prev->sz >= 0 && s[pos-1-prev->sz]-'a' == let)
			{
				if(nw == nullptr)
				{
					if(prev->sons[let] == nullptr)
					{
					prev->sons[let] = new node(&Oroot, prev->sz + 2);
					e = true;
					}
					nw = prev->sons[let];
					nw->val++;
					if(!e) break;
				}
				else
				{
					nw->sufLink = prev->sons[let];
					break;
				}
			}
			prev = prev->sufLink;
		}
		if(e)
		nw->sufLink->edg.push_back(nw);
		return nw;
	}
	long long res = 0;
	int dfs(node* a)
	{
		int sum = a->val;
		for(auto v : a->edg)
			sum += dfs(v);
		debug(a->sz);
		debug(sum);
		if(a->sz != -1)
		res = max(res, (long long)sum * (long long)(a->sz/2));
		return sum;
	}
	palTrie(string _s)
	{
		s = _s;
		int k = 0;
		node* p = &Oroot;
		for(auto v : s) p = add(v - 'a', k++, p);
		dfs(&Oroot);
	}
};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	char g = 'z' + 1;
	string t = "";
	t += g;
	for(auto v : s) {t += v; t += g;}
	s = t;
	debug(s);
	palTrie A(s);
	debug(A.res);
	cout<<A.res;
}

Compilation message (stderr)

palindrome.cpp: In member function 'palTrie::node* palTrie::add(char, int, palTrie::node*)':
palindrome.cpp:41:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |      if(prev->sons[let] == nullptr)
      |                    ^~~
palindrome.cpp:43:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |      prev->sons[let] = new node(&Oroot, prev->sz + 2);
      |                 ^~~
palindrome.cpp:46:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |      nw = prev->sons[let];
      |                      ^~~
palindrome.cpp:52:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |      nw->sufLink = prev->sons[let];
      |                               ^~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27