Submission #564938

#TimeUsernameProblemLanguageResultExecution timeMemory
564938ac2huPalindromes (APIO14_palindrome)C++14
47 / 100
1084 ms5444 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "../templates/debug.h" #else #define deb(x...) #endif using namespace std; const int C = 26; struct node{ node* child[C]; int cnt = 0; int dist = 0; }; node* make_node(int d){ node* temp = new node; for(int i = 0;i<C;i++){ temp->child[i] = NULL; } temp->cnt = 0; temp->dist = d; return temp; } string s; int ans = 0; node* root1 = make_node(-1); node* root2 = make_node(0); auto is_pali(int l,int r){ if(l > r)return true; if(s[l] != s[r])return false; return is_pali(l + 1, r - 1); } void add1(int l,int r){ node* trav = root1; for(int i = l;i<=r;i++){ int c = s[i] - 'a'; if(!trav->child[c]) trav->child[c] = make_node(trav->dist + 2); trav = trav->child[c]; ++trav->cnt; ans = max(ans, trav->cnt*trav->dist); } } void add2(int l,int r){ node* trav = root2; for(int i = l;i<=r;i++){ int c = s[i] - 'a'; if(!trav->child[c]) trav->child[c] = make_node(trav->dist + 2); trav = trav->child[c]; ++trav->cnt; ans = max(ans, trav->cnt*trav->dist); } } signed main(){ cin >> s; int n = s.size(); for(int i = 0;i<n;i++){ auto check = [&](int mid)->bool{ if(i - mid < 0)return false; if(i + mid > n - 1)return false; return is_pali(i - mid, i + mid); }; int l = 0,r = n; while(l<r){ int mid = (l + r + 1)/2; if(check(mid)){ l = mid; } else r = mid - 1; } add1(i,i + l); if(i > 0 && s[i] == s[i - 1]){ l = 0,r = n - 1; while(l < r){ int mid = (l + r + 1)/2; if(i - 1 - mid >= 0 && i + mid < n && is_pali(i - 1 - mid, i + mid)){ l = mid; } else r = mid - 1; } add2(i,i + l); } } 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...