# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
205590 | 2020-02-29T08:59:02 Z | mihai50000 | Palindromes (APIO14_palindrome) | C++17 | 51 ms | 30232 KB |
#include <bits/stdc++.h> using namespace std; #define int long long struct PalTree { struct Node { map <char, int> next; int link; int len; int cnt; }; vector <Node> T; int n = 2; int ans = 0; PalTree(string str) : T(str.size() + 2) { T[1].link = T[1].len = 0; T[0].link = T[0].len = -1; int last = 0; int m = str.size(); for(int i = 0; i < m; ++i) { char ch = str[i]; int nod = last; while(ch != str[i - 1 - T[nod].len]) nod = T[nod].link; if(T[nod].next.count(ch)) { nod = T[nod].next[ch]; T[nod].cnt++; last = nod; continue; } int act = n++; T[act].len = T[nod].len + 2; T[nod].next[ch] = act; int link = T[nod].link; while(link != -1) { if(ch == str[i - T[link].len - 1] && T[link].next.count(ch)) { link = T[link].next[ch]; break; } link = T[link].link; } if(link <= 0) link = 1; T[act].link = 1; T[act].cnt = 1; last = act; } for(int i = n - 1; i > 0; --i) { T[T[i].link].cnt += T[i].cnt; ans = max(ans, T[i].cnt * T[i].len); } } }; main() { string s; cin >> s; PalTree arb(s); cout << arb.ans << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 4 ms | 256 KB | Output is correct |
3 | Incorrect | 5 ms | 256 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 380 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1272 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 19 ms | 9720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 51 ms | 30232 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |