제출 #752781

#제출 시각아이디문제언어결과실행 시간메모리
752781Username4132회문 (APIO14_palindrome)C++14
73 / 100
149 ms131072 KiB
#include<iostream> using namespace std; using ll = long long; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) struct trie{ int cnt=0, total=0; trie *up[20], *nxt[28]={0}; }; const int MAXN=600015; int n, l=1, r=1, len[MAXN]; ll ans; trie *root, *pal[MAXN]; string str, aux; void dfs(trie* v, int d, bool yes){ v->total=v->cnt; forn(i, 28) if(v->nxt[i]){ dfs(v->nxt[i], d+1, yes^1); v->total+=v->nxt[i]->total; } if(yes) ans=max(ans, ((ll)d)*v->total); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> aux; str.resize(2*aux.size() + 1); str[0]='$'; forn(i, aux.size()) str[2*i+1]=aux[i]; forn(i, aux.size()-1) str[2*i + 2]='z'+1; str.back()='^'; n = str.size(); root = new trie; forn(i, 20) root->up[i]=root; forsn(i, 1, n-1){ trie* cur=NULL; if(i>=r) cur=root; else{ len[i]=min(r-i, len[l+r-i]); cur=pal[l+r-i]; int goUp=len[l+r-i]-len[i]; dforn(j, 20) if(goUp>=(1<<j)) goUp-=(1<<j), cur=cur->up[j]; } while(str[i+len[i]]==str[i-len[i]]){ int pos=str[i+len[i]]-'a'; ++len[i]; if(cur->nxt[pos]==NULL){ cur->nxt[pos]=new trie; trie** ptr=cur->nxt[pos]->up; ptr[0]=cur; forn(j, 19) ptr[j+1]=ptr[j]->up[j]; } cur=cur->nxt[pos]; } if(i+len[i]>r) r=i+len[i], l=i-len[i]; pal[i]=cur; cur->cnt++; } forn(i, 26) if(root->nxt[i]) dfs(root->nxt[i], 1, true); if(root->nxt[26]) dfs(root->nxt[26], 1, false); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...