# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
921426 | 2024-02-03T20:16:04 Z | AVIJIT_BISWAS | Palindromes (APIO14_palindrome) | C++14 | 18 ms | 36008 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long struct PalindromicTree { struct node { int nxt[26], len, link, occ; }; string s; vector<node> t; int sz, last; PalindromicTree() {} PalindromicTree(string _s) { s = _s; int n = s.size(); t.clear(); t.resize(n + 9); sz = 2, last = 2; t[1].len = -1, t[1].link = 1; t[2].len = 0, t[2].link = 1; } int extend(int pos) { // returns 1 if it creates a new palindrome int cur = last, curlen = 0; int ch = s[pos] - 'a'; while (1) { curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break; cur = t[cur].link; } if (t[cur].nxt[ch]) { last = t[cur].nxt[ch]; return 0; } sz++; last = sz; t[sz].len = t[cur].len + 2; t[cur].nxt[ch] = sz; ++t[last].occ; if (t[sz].len == 1) { t[sz].link = 2; return 1; } while (1) { cur = t[cur].link; curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { t[sz].link = t[cur].nxt[ch]; break; } } return 1; } }T; void solve() { string s; cin >> s; T = PalindromicTree(s); int n = s.size(); for(int i = 0; i < n; i++){ T.extend(i); } ll ans = 0; for(int i = T.sz; i > 2; i--) { T.t[T.t[i].link].occ += T.t[i].occ; ans = max(ans, 1ll * T.t[i].occ * T.t[i].len); } cout << ans << '\n'; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr);int t = 1; #ifndef ONLINE_JUDGE freopen("output.txt", "w", stderr); #endif // cin >> t; for(int i = 1; i <= t; i++){ //cout << "-----Case:" << i << "-----\n"; solve(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 452 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 460 KB | Output is correct |
9 | Correct | 0 ms | 456 KB | Output is correct |
10 | Correct | 0 ms | 456 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Incorrect | 0 ms | 348 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 600 KB | Output is correct |
10 | Incorrect | 0 ms | 348 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1628 KB | Output is correct |
2 | Correct | 1 ms | 1628 KB | Output is correct |
3 | Correct | 1 ms | 1488 KB | Output is correct |
4 | Correct | 1 ms | 1628 KB | Output is correct |
5 | Correct | 1 ms | 1628 KB | Output is correct |
6 | Correct | 1 ms | 1628 KB | Output is correct |
7 | Correct | 1 ms | 1500 KB | Output is correct |
8 | Incorrect | 1 ms | 1628 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 12120 KB | Output is correct |
2 | Correct | 5 ms | 12124 KB | Output is correct |
3 | Correct | 5 ms | 12124 KB | Output is correct |
4 | Correct | 5 ms | 12124 KB | Output is correct |
5 | Correct | 4 ms | 12124 KB | Output is correct |
6 | Correct | 4 ms | 12120 KB | Output is correct |
7 | Correct | 5 ms | 12120 KB | Output is correct |
8 | Incorrect | 5 ms | 12124 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 35812 KB | Output is correct |
2 | Correct | 14 ms | 35644 KB | Output is correct |
3 | Correct | 15 ms | 35812 KB | Output is correct |
4 | Correct | 15 ms | 36008 KB | Output is correct |
5 | Correct | 18 ms | 35756 KB | Output is correct |
6 | Correct | 14 ms | 35812 KB | Output is correct |
7 | Correct | 15 ms | 35812 KB | Output is correct |
8 | Incorrect | 13 ms | 35812 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |