oj.uz

Submission #397598

# Submission time Handle Problem Language Result Execution time Memory
397598 2021-05-02T13:44:25 Z Drew_ Palindromes (APIO14_palindrome) C++14
100 / 100
 60 ms 54880 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define ll long long
#define pb push_back

const int MAX = 3e5 + 7;

struct Node
{
	int l, r;
	int len, occ = 0;

	int ch[26]; //adding a character
	int slink; //suffix link
};

int sz, cur;
Node tree[MAX]; //eertree

string s;
void addChar(int idx)
{
	int tmp = cur;
	while (1)
	{
		if (idx - tree[tmp].len >= 1 && s[idx] == s[idx - tree[tmp].len - 1])
			break;
		tmp = tree[tmp].slink;
	}

	if (tree[tmp].ch[s[idx] - 'a'] != 0)
	{
		cur = tree[tmp].ch[s[idx] - 'a'];
		return;
	}

	sz++;
	tree[tmp].ch[s[idx] - 'a'] = sz;
	tree[sz].len = tree[tmp].len + 2;
	tree[sz].r = idx;
	tree[sz].l = idx - tree[sz].len + 1;

	//getting suffix link
	tmp = tree[tmp].slink;
	cur = sz;
	if (tree[cur].len == 1)
	{
		tree[cur].slink = 2;
		return;
	}

	while (1)
	{
		if (idx - tree[tmp].len >= 1 && s[idx] == s[idx - tree[tmp].len - 1])
			break;
		tmp = tree[tmp].slink;
	}

	tree[cur].slink = tree[tmp].ch[s[idx] - 'a'];
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	tree[1].len = -1;
	tree[1].slink = 1;
	tree[2].len = 0;
	tree[2].slink = 1;
	sz = 2; cur = 1;

	cin >> s;
	for (int i = 0; i < s.size(); ++i)
	{
		addChar(i);
		tree[cur].occ++;
	}

	ll res = 0;

	int indegree[MAX];
	vector<int> adj[MAX];
	queue<int> q;
	for (int i = 3; i <= sz; ++i)
	{
		adj[i].pb(tree[i].slink);
		indegree[tree[i].slink]++;
	}

	for (int i = 3; i <= sz; ++i)
		if (indegree[i] == 0)
			q.push(i);

	while (!q.empty())
	{
		int node = q.front();
		q.pop();

		res = max(res, 1LL * tree[node].len * tree[node].occ);

		for (int to : adj[node])
		{
			tree[to].occ += tree[node].occ;
			
			indegree[to]--;
			if (indegree[to] == 0)
				q.push(to);
		}
	}
	cout << res << '\n';

	return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < s.size(); ++i)
      |                  ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43724 KB Output is correct
2 Correct 22 ms 43720 KB Output is correct
3 Correct 22 ms 43724 KB Output is correct
4 Correct 22 ms 43724 KB Output is correct
5 Correct 21 ms 43652 KB Output is correct
6 Correct 22 ms 43664 KB Output is correct
7 Correct 22 ms 43664 KB Output is correct
8 Correct 22 ms 43720 KB Output is correct
9 Correct 21 ms 43716 KB Output is correct
10 Correct 22 ms 43716 KB Output is correct
11 Correct 22 ms 43724 KB Output is correct
12 Correct 22 ms 43648 KB Output is correct
13 Correct 22 ms 43720 KB Output is correct
14 Correct 21 ms 43720 KB Output is correct
15 Correct 25 ms 43680 KB Output is correct
16 Correct 22 ms 43648 KB Output is correct
17 Correct 25 ms 43748 KB Output is correct
18 Correct 22 ms 43672 KB Output is correct
19 Correct 21 ms 43724 KB Output is correct
20 Correct 22 ms 43724 KB Output is correct
21 Correct 22 ms 43660 KB Output is correct
22 Correct 22 ms 43644 KB Output is correct
23 Correct 22 ms 43720 KB Output is correct
24 Correct 22 ms 43656 KB Output is correct
25 Correct 22 ms 43732 KB Output is correct
26 Correct 22 ms 43680 KB Output is correct
27 Correct 20 ms 43744 KB Output is correct
28 Correct 22 ms 43724 KB Output is correct
29 Correct 21 ms 43752 KB Output is correct
30 Correct 22 ms 43760 KB Output is correct
31 Correct 21 ms 43760 KB Output is correct
32 Correct 20 ms 43724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43780 KB Output is correct
2 Correct 23 ms 43740 KB Output is correct
3 Correct 22 ms 43700 KB Output is correct
4 Correct 22 ms 43700 KB Output is correct
5 Correct 22 ms 43724 KB Output is correct
6 Correct 22 ms 43752 KB Output is correct
7 Correct 22 ms 43724 KB Output is correct
8 Correct 23 ms 43744 KB Output is correct
9 Correct 22 ms 43760 KB Output is correct
10 Correct 20 ms 43724 KB Output is correct
11 Correct 22 ms 43724 KB Output is correct
12 Correct 22 ms 43756 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44072 KB Output is correct
2 Correct 23 ms 44072 KB Output is correct
3 Correct 23 ms 44044 KB Output is correct
4 Correct 24 ms 44128 KB Output is correct
5 Correct 22 ms 44100 KB Output is correct
6 Correct 22 ms 44036 KB Output is correct
7 Correct 23 ms 44108 KB Output is correct
8 Correct 22 ms 43708 KB Output is correct
9 Correct 22 ms 43784 KB Output is correct
10 Correct 21 ms 44032 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47324 KB Output is correct
2 Correct 33 ms 47428 KB Output is correct
3 Correct 37 ms 47452 KB Output is correct
4 Correct 34 ms 47480 KB Output is correct
5 Correct 35 ms 47436 KB Output is correct
6 Correct 31 ms 46416 KB Output is correct
7 Correct 32 ms 46940 KB Output is correct
8 Correct 24 ms 44036 KB Output is correct
9 Correct 26 ms 44660 KB Output is correct
10 Correct 31 ms 46916 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 54604 KB Output is correct
2 Correct 60 ms 54872 KB Output is correct
3 Correct 52 ms 54856 KB Output is correct
4 Correct 53 ms 54860 KB Output is correct
5 Correct 59 ms 54864 KB Output is correct
6 Correct 53 ms 53740 KB Output is correct
7 Correct 55 ms 53076 KB Output is correct
8 Correct 28 ms 44504 KB Output is correct
9 Correct 28 ms 44368 KB Output is correct
10 Correct 50 ms 52976 KB Output is correct
11 Correct 57 ms 54880 KB Output is correct
12 Correct 32 ms 45268 KB Output is correct