oj.uz

Submission #49591

# Submission time Handle Problem Language Result Execution time Memory
49591 2018-05-31T18:57:59 Z jcg Palindromes (APIO14_palindrome) C++14
100 / 100
 96 ms 66400 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

template<typename charT, typename Container>
struct palindromic_tree
{
	struct node
	{
		int slink;
		int length;
		Container next;
		node(int slink, int length) : slink(slink), length(length), next{{}} {}
		int operator[](int c) const { return next[c]; }
		int& operator[](int c) { return next[c]; }
	};

	palindromic_tree()
	{
		sink = 0;
		nodes.emplace_back(0, -1);
		nodes.emplace_back(0, 0);
	}

	int extend(const charT &c)
	{
		str.push_back(c);
		sink = get_link(sink);
		if (!nodes[sink][c])
		{
			nodes[sink][c] = nodes.size();
			int length = nodes[sink].length + 2;
			int slink = length == 1 ? 1 : nodes[get_link(nodes[sink].slink)][c];
			nodes.emplace_back(slink, length);
		}
		return sink = nodes[sink][c];
	}

	const node& operator[](int node_id) const { return nodes[node_id]; }
	int size() const { return nodes.size(); }

private:
	int sink;
	vector<node> nodes;
	vector<charT> str;

	int get_link(int v)
	{
		int n = str.size();
		while (n - nodes[v].length - 2 < 0 || str[n - 1] != str[n - nodes[v].length - 2])
			v = nodes[v].slink;
		return v;
	}
};

int main()
{
#ifdef jcg
	assert(freopen("input.in", "r", stdin));
	// assert(freopen("output.out", "w", stdout));
#else
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;

	palindromic_tree<int, array<int, 26>> tree;

	vector<int> endpos;
	for (char c : s)
		endpos.emplace_back(tree.extend(c-'a'));

	vector<int> occ(tree.size());
	for (int x : endpos) ++occ[x];

	long long ans = 0;
	for (int i = (int) tree.size()-1; i >= 2; --i)
	{
		ans = max(ans, (long long) tree[i].length * occ[i]);
		occ[tree[i].slink] += occ[i];
	}

	cout << ans << endl;

	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 3 ms 900 KB Output is correct
3 Correct 3 ms 904 KB Output is correct
4 Correct 2 ms 1036 KB Output is correct
5 Correct 2 ms 1036 KB Output is correct
6 Correct 3 ms 1036 KB Output is correct
7 Correct 2 ms 1036 KB Output is correct
8 Correct 3 ms 1036 KB Output is correct
9 Correct 3 ms 1036 KB Output is correct
10 Correct 3 ms 1036 KB Output is correct
11 Correct 2 ms 1036 KB Output is correct
12 Correct 2 ms 1036 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2756 KB Output is correct
2 Correct 6 ms 2828 KB Output is correct
3 Correct 5 ms 2828 KB Output is correct
4 Correct 5 ms 2860 KB Output is correct
5 Correct 4 ms 2860 KB Output is correct
6 Correct 5 ms 2860 KB Output is correct
7 Correct 5 ms 2860 KB Output is correct
8 Correct 3 ms 2860 KB Output is correct
9 Correct 2 ms 2860 KB Output is correct
10 Correct 4 ms 2860 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16504 KB Output is correct
2 Correct 26 ms 16620 KB Output is correct
3 Correct 23 ms 16720 KB Output is correct
4 Correct 25 ms 16720 KB Output is correct
5 Correct 26 ms 16788 KB Output is correct
6 Correct 22 ms 17276 KB Output is correct
7 Correct 23 ms 17376 KB Output is correct
8 Correct 6 ms 17376 KB Output is correct
9 Correct 10 ms 17376 KB Output is correct
10 Correct 27 ms 17720 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 63364 KB Output is correct
2 Correct 84 ms 64696 KB Output is correct
3 Correct 83 ms 64696 KB Output is correct
4 Correct 92 ms 64696 KB Output is correct
5 Correct 82 ms 64696 KB Output is correct
6 Correct 82 ms 66004 KB Output is correct
7 Correct 59 ms 66004 KB Output is correct
8 Correct 14 ms 66004 KB Output is correct
9 Correct 13 ms 66004 KB Output is correct
10 Correct 54 ms 66004 KB Output is correct
11 Correct 96 ms 66400 KB Output is correct
12 Correct 18 ms 66400 KB Output is correct