# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
941225 | 2024-03-08T10:20:56 Z | wii | Palindromes (APIO14_palindrome) | C++17 | 24 ms | 49884 KB |
#include <bits/stdc++.h> using namespace std; typedef double db; typedef long long ll; typedef long double ld; #define int ll typedef pair<int, int> pii; #define lx (id << 1) #define rx (lx | 1) #define gcd __gcd #define pb push_back #define all(x) (x).begin(), (x).end() #define bit(i, mask) ((mask) >> (i) & 1) #define reset(x, val) memset(x, val, sizeof(x)) #define foru(i,a,b) for(int i = (a); i <= (b); ++i) #define ford(i,a,b) for(int i = (a); i >= (b); --i) #define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; } template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; } const ll Linf = 0x3f3f3f3f3f3f3f3f; const int Inf = 0x3f3f3f3f; const ll Mod = 1e9 + 7; const ll Mod2 = ll(1e9) + 9; const int Lim = 1e6 + 5; const int inv6 = 166666668; /// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*==== const int base = 3; const int N = 3e5 + 5; const int K = log2(N) + 1; const int dx[] = {+1, -1, 0, 0}; const int dy[] = {0, 0, +1, -1}; const int block_size = sqrt(2e9) + 2; const int MAXN = 105000; struct node { int next[26]; int len; int sufflink; int num; }; int len; string s; node tree[MAXN]; int num; // node 1 - root with len -1, node 2 - root with len 0 int suff; // max suffix palindrome long long ans; bool addLetter(int pos) { int cur = suff, curlen = 0; int let = s[pos] - 'a'; while (true) { curlen = tree[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break; cur = tree[cur].sufflink; } if (tree[cur].next[let]) { suff = tree[cur].next[let]; return false; } num++; suff = num; tree[num].len = tree[cur].len + 2; tree[cur].next[let] = num; if (tree[num].len == 1) { tree[num].sufflink = 2; return true; } while (true) { cur = tree[cur].sufflink; curlen = tree[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { tree[num].sufflink = tree[cur].next[let]; break; } } return true; } // mqmwmmmmmemrmtymmmmmmmmqwertyeeeeeeeee void solve() { cin >> s; num = 2; suff = 2; tree[1].len = -1; tree[2].sufflink = 1; tree[2].len = 0; tree[2].sufflink = 1; for (int i = 0; i < s.size(); ++i) { int sc = addLetter(i); ++tree[suff].num; } int ans = 0; for (int i = num; i >= 3; --i) { tree[tree[i].sufflink].num += tree[i].num; maximize(ans, tree[i].len * tree[i].num); } cout << ans; } signed main() { FastIO; #define task "test" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } #define task "palindrome" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int ntest = 1; // cin >> ntest; while (ntest--) { //cout << "Case " << q << ": " << "\n"; solve(); cout << "\n"; } return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 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 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 344 KB | Output is correct |
20 | Correct | 0 ms | 344 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 344 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 1 ms | 460 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 1 ms | 344 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2648 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2648 KB | Output is correct |
7 | Correct | 1 ms | 2652 KB | Output is correct |
8 | Correct | 1 ms | 2652 KB | Output is correct |
9 | Correct | 1 ms | 2652 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 2652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4696 KB | Output is correct |
2 | Correct | 1 ms | 4700 KB | Output is correct |
3 | Correct | 1 ms | 4696 KB | Output is correct |
4 | Correct | 1 ms | 4952 KB | Output is correct |
5 | Correct | 1 ms | 4772 KB | Output is correct |
6 | Correct | 1 ms | 4696 KB | Output is correct |
7 | Correct | 1 ms | 4700 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 23384 KB | Output is correct |
2 | Correct | 5 ms | 23384 KB | Output is correct |
3 | Correct | 6 ms | 23388 KB | Output is correct |
4 | Correct | 5 ms | 23388 KB | Output is correct |
5 | Correct | 6 ms | 23492 KB | Output is correct |
6 | Correct | 5 ms | 17240 KB | Output is correct |
7 | Correct | 5 ms | 21340 KB | Output is correct |
8 | Correct | 2 ms | 2904 KB | Output is correct |
9 | Correct | 2 ms | 7000 KB | Output is correct |
10 | Correct | 5 ms | 21340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 24 ms | 49884 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |