oj.uz

Submission #1119856

# Submission time Handle Problem Language Result Execution time Memory
1119856 2024-11-27T14:06:23 Z raczek Palindromes (APIO14_palindrome) C++17
100 / 100
 321 ms 93020 KB 
#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.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3312 KB Output is correct
2 Correct 7 ms 3152 KB Output is correct
3 Correct 6 ms 3408 KB Output is correct
4 Correct 6 ms 3408 KB Output is correct
5 Correct 5 ms 2896 KB Output is correct
6 Correct 5 ms 2896 KB Output is correct
7 Correct 5 ms 3164 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 4 ms 2128 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 30568 KB Output is correct
2 Correct 83 ms 29800 KB Output is correct
3 Correct 59 ms 31956 KB Output is correct
4 Correct 58 ms 31032 KB Output is correct
5 Correct 73 ms 25712 KB Output is correct
6 Correct 52 ms 19536 KB Output is correct
7 Correct 46 ms 23472 KB Output is correct
8 Correct 7 ms 1520 KB Output is correct
9 Correct 18 ms 8328 KB Output is correct
10 Correct 68 ms 21076 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 88280 KB Output is correct
2 Correct 288 ms 84940 KB Output is correct
3 Correct 181 ms 93020 KB Output is correct
4 Correct 204 ms 86988 KB Output is correct
5 Correct 321 ms 76156 KB Output is correct
6 Correct 228 ms 75380 KB Output is correct
7 Correct 252 ms 70592 KB Output is correct
8 Correct 23 ms 3320 KB Output is correct
9 Correct 20 ms 3348 KB Output is correct
10 Correct 267 ms 63084 KB Output is correct
11 Correct 294 ms 85192 KB Output is correct
12 Correct 32 ms 11628 KB Output is correct