oj.uz

Submission #555972

# Submission time Handle Problem Language Result Execution time Memory
555972 2022-05-02T03:07:35 Z hollwo_pelw Palindromes (APIO14_palindrome) C++17
100 / 100
 24 ms 34948 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen("hollwo_pelw.inp", "r"))
		assert(freopen("hollwo_pelw.inp", "r", stdin)), assert(freopen("hollwo_pelw.out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 3e5 + 5;

int n, siz[N], cnt[N], slink[N], tr[N][26], nnode = 1;
char s[N];

void Hollwo_Pelw(){
	cin >> (s + 1), n = strlen(s + 1);
	siz[0] = -1;
	for (int i = 1, c = 1; i <= n; i++) {
		while (s[i] != s[i - siz[c] - 1])
			c = slink[c];

		if (!tr[c][s[i] - 'a']) {
			int p = slink[c];
			while (s[i] != s[i - siz[p] - 1])
				p = slink[p];
			p = max(1, tr[p][s[i] - 'a']);

			tr[c][s[i] - 'a'] = ++ nnode;
			slink[nnode] = p, siz[nnode] = siz[c] + 2;
		}
		cnt[c = tr[c][s[i] - 'a']] ++;
	}

	long long res = 0;

	for (int i = nnode; i; i--) {
		cnt[slink[i]] += cnt[i];
		res = max(res, 1ll * cnt[i] * siz[i]);
	}

	cout << res << '\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1488 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11832 KB Output is correct
2 Correct 9 ms 11864 KB Output is correct
3 Correct 8 ms 11868 KB Output is correct
4 Correct 8 ms 11848 KB Output is correct
5 Correct 8 ms 11864 KB Output is correct
6 Correct 8 ms 8788 KB Output is correct
7 Correct 8 ms 10040 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 3156 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 34880 KB Output is correct
2 Correct 23 ms 34948 KB Output is correct
3 Correct 24 ms 34936 KB Output is correct
4 Correct 24 ms 34824 KB Output is correct
5 Correct 24 ms 34892 KB Output is correct
6 Correct 21 ms 31084 KB Output is correct
7 Correct 21 ms 29156 KB Output is correct
8 Correct 5 ms 992 KB Output is correct
9 Correct 5 ms 984 KB Output is correct
10 Correct 20 ms 28740 KB Output is correct
11 Correct 23 ms 34848 KB Output is correct
12 Correct 6 ms 4308 KB Output is correct