Submission #1150640

#TimeUsernameProblemLanguageResultExecution timeMemory
1150640SmuggingSpunPalindromes (APIO14_palindrome)C++20
0 / 100
0 ms324 KiB
#include<bits/stdc++.h> #define taskname "A" using namespace std; typedef long long ll; template<class T>void maximize(T& a, T b){ if(a < b){ a = b; } } string s; ll ans = 0; struct Node{ int link, len, cnt, child[26]; Node(){ memset(this->child, -1, sizeof(this->child)); this->cnt = 0; } }; vector<Node>eer(2); void dfs(int s){ for(int i = 0; i < 26; i++){ if(eer[s].child[i] != -1){ dfs(eer[s].child[i]); } } eer[eer[s].link].cnt += eer[s].cnt; maximize(ans, 1LL * eer[s].cnt * eer[s].len); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); } eer[eer[1].len = eer[0].link = eer[1].link = 0].len = -1; cin >> s; for(int i = 0, root = 0; i < s.size(); i++){ s[i] -= 97; while(i - eer[root].len < 1 || s[i] != s[i - eer[root].len - 1]){ root = eer[root].link; } if(eer[root].child[s[i]] == -1){ int cur = eer[root].child[s[i]] = eer.size(); eer.emplace_back(Node()); if((eer[cur].len = eer[root].len + 2) > 1){ int r = root; while(true){ if(i - eer[r = eer[r].link].len > 0 && s[i - eer[r].len - 1] == s[i]){ eer[cur].link = eer[r].child[s[i]]; break; } } } else{ eer[cur].link = 0; } } eer[root = eer[root].child[s[i]]].cnt++; } dfs(0); dfs(1); cout << ans; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:32:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...