Submission #1119856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119856		raczek	Palindromes (APIO14_palindrome)	C++17	100 / 100	321 ms	93020 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
int cnt = 0;
struct node
{
	vector<node*> edg;
	node* sufLink = nullptr;
	int idx = 0;
	int val = 0;
	int sz = -1;
	node(node* suf, int s){
		idx = cnt++;
		sufLink = suf, sz = s;
	}
	node(){idx = cnt++;} 
};
unordered_map<int, node*> sons;
struct palTrie
{
	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(sons[prev->idx*30+let] == nullptr)
					{
					sons[prev->idx*30+let] 
					= new node(&Oroot, prev->sz + 2);
					e = true;
					}
					nw = sons[prev->idx*30+let];
					nw->val++;
					if(!e) break;
				}
				else
				{
					nw->sufLink = sons[prev->idx*30+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;
}

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