oj.uz

Submission #1117467

# Submission time Handle Problem Language Result Execution time Memory
1117467 2024-11-23T18:43:35 Z mat_jur Palindromes (APIO14_palindrome) C++17
73 / 100
 110 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int A = 27;

struct trie_node {
	int depth; 
	trie_node* parent;
	trie_node* e[A];
	int cnt;

	trie_node() {
		depth = 0;
		parent = nullptr;
		for (int i = 0; i < A; ++i) e[i] = nullptr;
		cnt = 0;
	}
};

void add_edge(trie_node *v, char c) {
	assert(v != nullptr);
	int x = c - 'a';
	if (v->e[x] != nullptr) return;
	trie_node *u = v->e[x] = new trie_node;
	u->depth = v->depth + 1;
	u->parent = v;
}

ll dfs(trie_node *v) {
	ll res = 0;
	for (int i = 0; i < A; ++i) {
		if (v->e[i] != nullptr) {
			res = max(res, dfs(v->e[i]));
			v->cnt += v->e[i]->cnt;
#ifdef DEBUG
			delete v->e[i];
#endif
		}
	}

	return max(res, ll(v->cnt) * ll(v->depth - 1));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	string s;
	cin >> s;
	int n = ssize(s);

	char filler = 'z' + 1;
	string tmp;
	tmp.push_back(filler);
	for (char x : s) {
		tmp.push_back(x);
		tmp.push_back(filler);
	}

	s = tmp;
	n = ssize(s);

	debug(s);

	vector<int> r(n);
	int f = 0;
	r[0] = 1;

	vector<trie_node*> Node(n+1);
	Node[0] = new trie_node;
	add_edge(Node[0], s[0]);
	Node[1] = Node[0]->e[s[0]-'a'];

	for (int i = 1; i < n; ++i) {
		int parent = 0;
		r[i] = 0;
		if (f + r[f] - 1 >= i) {
			int sym = 2*f - i;
			if (sym >= 0) r[i] = max(r[i], min(r[sym], sym - (f - r[f])));
			parent = sym+1;	
		}

		cerr << i+1 << ' ' << r[i] << '\n';
		debug(parent);

		int v = i+1;
		Node[v] = Node[parent];
		while (Node[v]->depth != r[i]) Node[v] = Node[v]->parent;

		while (i - r[i] >= 0 && i + r[i] < n && s[i-r[i]] == s[i+r[i]]) {
			add_edge(Node[v], s[i+r[i]]);
			Node[v] = Node[v]->e[s[i+r[i]]-'a'];
			r[i]++;
		}

		Node[v]->cnt++;
 
		if (i + r[i] >= f + r[f]) f = i;
	}

	ll res = dfs(Node[0]);
//	for (int i = 0; i < A-1; ++i) {
//		if (Node[0]->e[i] != nullptr) {
//			res = max(res, dfs(Node[0]->e[i], 1));
//#ifdef DEBUG
//			delete Node[0]->e[i];
//#endif
//		}
//	}
//	if (Node[0]->e[A-1] != nullptr) {
//		res = max(res, dfs(Node[0]->e[A-1], 1));
//#ifdef DEBUG
//			delete Node[0]->e[A-1];
//#endif
//	}

#ifdef DEBUG
	delete Node[0];
#endif

	cout << res << '\n';

	return 0;
}

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 456 KB Output is correct
8 Correct 1 ms 504 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 504 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 460 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 592 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 456 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 848 KB Output is correct
2 Correct 1 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 420 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 848 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6224 KB Output is correct
2 Correct 7 ms 5968 KB Output is correct
3 Correct 6 ms 6224 KB Output is correct
4 Correct 6 ms 5968 KB Output is correct
5 Correct 6 ms 5968 KB Output is correct
6 Correct 5 ms 5968 KB Output is correct
7 Correct 5 ms 5712 KB Output is correct
8 Correct 2 ms 1012 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 4 ms 4256 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 57916 KB Output is correct
2 Correct 68 ms 55796 KB Output is correct
3 Correct 57 ms 57936 KB Output is correct
4 Correct 66 ms 56296 KB Output is correct
5 Correct 50 ms 56396 KB Output is correct
6 Correct 52 ms 41276 KB Output is correct
7 Correct 52 ms 46376 KB Output is correct
8 Correct 7 ms 3652 KB Output is correct
9 Correct 20 ms 16052 KB Output is correct
10 Correct 46 ms 48768 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -