Submission #764268

#TimeUsernameProblemLanguageResultExecution timeMemory
764268Ahmed57Palindromes (APIO14_palindrome)C++17
47 / 100
1078 ms9544 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; //TRIE struct node{ node *nxt[26]; int is; node(){ is = 0; for(int i = 0;i<26;i++){ nxt[i] = NULL; } } }; void inser(string w,node *root){ for(auto ch:w){ if(root->nxt[ch-'a']==NULL){ root->nxt[ch-'a'] = new node(); } root=root->nxt[ch-'a']; root->is ++; } } vector<int> manacher_odd(string s) { int n = s.size(); s = "$" + s + "^"; vector<int> p(n + 2); int l = 1, r = 1; for(int i = 1; i <= n; i++) { p[i] = max(0, min(r - i, p[l + (r - i)])); while(s[i - p[i]] == s[i + p[i]]) { p[i]++; } if(i + p[i] > r) { l = i - p[i], r = i + p[i]; } } return vector<int>(begin(p) + 1, end(p) - 1); } vector<int> manacher(string s) { string t; for(auto c: s) { t += string("#") + c; } auto res = manacher_odd(t + "#"); return vector<int>(begin(res) + 1, end(res) - 1); } long long all = 0; void dfs(node *root,int v,long long dep){ all = max(all,root->is*(dep*2-v)); for(int i = 0;i<26;i++){ if(root->nxt[i]!=NULL){ dfs(root->nxt[i],v,dep+1); } } } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); node *rootOdd = new node(); node *rootEven = new node(); string s;cin>>s; vector<int> lol = manacher(s); for(int i = 0;i<lol.size();i++){ long long x = lol[i]/2; if(i%2==0){ int l = i/2; string ss; while(x--){ ss+=s[l++]; } inser(ss,rootOdd); }else{ int l = i/2+1; string ss; while(x--){ ss+=s[l++]; } inser(ss,rootEven); } } dfs(rootEven,0,0); dfs(rootOdd,1,0); cout<<all<<"\n"; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0;i<lol.size();i++){
      |                   ~^~~~~~~~~~~
#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...