Submission #440220

#TimeUsernameProblemLanguageResultExecution timeMemory
440220keta_tsimakuridze회문 (APIO14_palindrome)C++14
100 / 100
107 ms90156 KiB
#include<bits/stdc++.h> #define f first #define s second #define int long long using namespace std; const int N=3e5+5,mod=1e9+7; int t,in[N],idx,suff; vector<int>V[N]; string s; queue<int> q; struct st{ int vis[27]; int sufflink; int cnt; int len; } tree[N]; void add(int i){ int cur = suff; while(true) { if(s[i - tree[cur].len - 1] == s[i]) { if(tree[cur].vis[s[i]-'a']) { suff = tree[cur].vis[s[i]-'a']; tree[suff].cnt++; return; } suff = ++idx; tree[idx].cnt = 1; tree[cur].vis[s[i]-'a'] = idx; tree[idx].len = tree[cur].len + 2; break; } cur = tree[cur].sufflink; } if(tree[idx].len == 1){ tree[idx].sufflink = 2; return; } while(true) { cur = tree[cur].sufflink; if(s[i - tree[cur].len - 1] == s[i]) { tree[idx].sufflink = tree[cur].vis[s[i]-'a']; V[idx].push_back(tree[cur].vis[s[i]-'a']); in[tree[cur].vis[s[i]-'a']]++; break; } } } main(){ cin>>s; int n = s.size(); s = '#' + s; idx = 2; tree[1].len = -1; tree[2].len = 0; in[1] +=2; tree[1].sufflink = tree[2].sufflink = 1; suff = 2; for(int i=1;i<=n;i++){ add(i); } for(int i=1;i<=idx;i++) { if(!in[i]) q.push(i); } int ans = 0; while(q.size()){ int u = q.front(); q.pop(); ans = max(ans, tree[u].len * tree[u].cnt); for(int i=0;i<V[u].size();i++) { in[V[u][i]]--; tree[V[u][i]].cnt += tree[u].cnt; if(!in[V[u][i]]) q.push(V[u][i]); } } cout<<ans; }

Compilation message (stderr)

palindrome.cpp:51:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 |  main(){
      |  ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:72:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0;i<V[u].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...