# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
313178 | 2020-10-15T12:16:35 Z | vipghn2003 | Palindromes (APIO14_palindrome) | C++14 | 108 ms | 108928 KB |
#include <bits/stdc++.h> using namespace std; const int N=3e5+5; struct Node { int nxt[26],sufflink; int len,cnt; vector<int>edges; } tree[N*2]; string s; int suff, num; long long ans=0; void add_letter(int pos) { int curr=suff; int curr_len=0; int letter=s[pos]-'a'; while(true) { curr_len=tree[curr].len; if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos]) break; curr=tree[curr].sufflink; } if(tree[curr].nxt[letter]) { suff=tree[curr].nxt[letter]; tree[suff].cnt++; return; } suff=++num; tree[num].len=tree[curr].len+2; tree[num].cnt=1; tree[curr].nxt[letter]=num; if(tree[num].len==1) { tree[num].sufflink=2; tree[2].edges.push_back(num); return; } while(true) { curr=tree[curr].sufflink; curr_len=tree[curr].len; if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos]) { tree[num].sufflink=tree[curr].nxt[letter]; tree[tree[curr].nxt[letter]].edges.push_back(num); break; } } } void init() { num=2; suff=2; tree[1].len=-1; tree[1].sufflink=1; tree[2].len=0; tree[2].sufflink=1; tree[1].edges.push_back(2); } void dfs(int node=1) { for(auto&i:tree[node].edges) { dfs(i); tree[node].cnt+=tree[i].cnt; } ans=max(ans,1ll*tree[node].len*tree[node].cnt); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> s; init(); for(int i=0;i<s.size();i++) add_letter(i); dfs(); cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 84992 KB | Output is correct |
2 | Correct | 46 ms | 84856 KB | Output is correct |
3 | Correct | 46 ms | 84864 KB | Output is correct |
4 | Correct | 45 ms | 84856 KB | Output is correct |
5 | Correct | 46 ms | 84856 KB | Output is correct |
6 | Correct | 47 ms | 84992 KB | Output is correct |
7 | Correct | 46 ms | 84856 KB | Output is correct |
8 | Correct | 46 ms | 84984 KB | Output is correct |
9 | Correct | 46 ms | 84856 KB | Output is correct |
10 | Correct | 47 ms | 84928 KB | Output is correct |
11 | Correct | 46 ms | 84992 KB | Output is correct |
12 | Correct | 46 ms | 84856 KB | Output is correct |
13 | Correct | 46 ms | 84856 KB | Output is correct |
14 | Correct | 46 ms | 84984 KB | Output is correct |
15 | Correct | 46 ms | 84856 KB | Output is correct |
16 | Correct | 47 ms | 84984 KB | Output is correct |
17 | Correct | 46 ms | 84856 KB | Output is correct |
18 | Correct | 46 ms | 84856 KB | Output is correct |
19 | Correct | 46 ms | 84872 KB | Output is correct |
20 | Correct | 47 ms | 84856 KB | Output is correct |
21 | Correct | 46 ms | 84884 KB | Output is correct |
22 | Correct | 46 ms | 84856 KB | Output is correct |
23 | Correct | 47 ms | 84856 KB | Output is correct |
24 | Correct | 46 ms | 84856 KB | Output is correct |
25 | Correct | 46 ms | 84856 KB | Output is correct |
26 | Correct | 47 ms | 84856 KB | Output is correct |
27 | Correct | 46 ms | 84856 KB | Output is correct |
28 | Correct | 46 ms | 84856 KB | Output is correct |
29 | Correct | 45 ms | 84856 KB | Output is correct |
30 | Correct | 46 ms | 84984 KB | Output is correct |
31 | Correct | 46 ms | 84888 KB | Output is correct |
32 | Correct | 46 ms | 84856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 84864 KB | Output is correct |
2 | Correct | 47 ms | 84856 KB | Output is correct |
3 | Correct | 46 ms | 84984 KB | Output is correct |
4 | Correct | 46 ms | 84856 KB | Output is correct |
5 | Correct | 46 ms | 84876 KB | Output is correct |
6 | Correct | 46 ms | 84984 KB | Output is correct |
7 | Correct | 46 ms | 84856 KB | Output is correct |
8 | Correct | 47 ms | 84856 KB | Output is correct |
9 | Correct | 46 ms | 84864 KB | Output is correct |
10 | Correct | 47 ms | 84860 KB | Output is correct |
11 | Correct | 46 ms | 84856 KB | Output is correct |
12 | Correct | 47 ms | 84856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 85368 KB | Output is correct |
2 | Correct | 48 ms | 85384 KB | Output is correct |
3 | Correct | 48 ms | 85624 KB | Output is correct |
4 | Correct | 46 ms | 85632 KB | Output is correct |
5 | Correct | 49 ms | 84984 KB | Output is correct |
6 | Correct | 47 ms | 85112 KB | Output is correct |
7 | Correct | 47 ms | 85240 KB | Output is correct |
8 | Correct | 46 ms | 84860 KB | Output is correct |
9 | Correct | 46 ms | 84984 KB | Output is correct |
10 | Correct | 47 ms | 84984 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 90488 KB | Output is correct |
2 | Correct | 59 ms | 89464 KB | Output is correct |
3 | Correct | 59 ms | 92920 KB | Output is correct |
4 | Correct | 58 ms | 91128 KB | Output is correct |
5 | Correct | 63 ms | 86264 KB | Output is correct |
6 | Correct | 55 ms | 87108 KB | Output is correct |
7 | Correct | 58 ms | 88056 KB | Output is correct |
8 | Correct | 48 ms | 85240 KB | Output is correct |
9 | Correct | 50 ms | 86776 KB | Output is correct |
10 | Correct | 59 ms | 86012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 101888 KB | Output is correct |
2 | Correct | 85 ms | 96896 KB | Output is correct |
3 | Correct | 86 ms | 108928 KB | Output is correct |
4 | Correct | 81 ms | 99968 KB | Output is correct |
5 | Correct | 108 ms | 89984 KB | Output is correct |
6 | Correct | 83 ms | 95744 KB | Output is correct |
7 | Correct | 78 ms | 93952 KB | Output is correct |
8 | Correct | 52 ms | 85760 KB | Output is correct |
9 | Correct | 53 ms | 85760 KB | Output is correct |
10 | Correct | 91 ms | 89088 KB | Output is correct |
11 | Correct | 90 ms | 97152 KB | Output is correct |
12 | Correct | 55 ms | 87552 KB | Output is correct |