Submission #157660

#	Time	Username	Problem	Language	Result	Execution time	Memory
157660		sadmanrizwan	Palindromes (APIO14_palindrome)	C++14	100 / 100	108 ms	50552 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=300005;
struct node{
    int len,link,cnt;
    map <char,int> to;
};
node pt[MX];
int size,last;
char s[MX];
bool vis[MX];
vector <int> idx[MX];
void init_node(int n)
{
    pt[n].len=0;
    pt[n].cnt=0;
    pt[n].link=-1;
    pt[n].to.clear();
}
void init_pt()
{
    init_node(0);
    init_node(1);
    pt[0].len=pt[0].link=-1;
    pt[1].link=0;
    size=2,last=1;
}
int find(int n,char s[],int i)
{
    while(n){
        int j=i-pt[n].len-1;
        if(j>=0 && s[i]==s[j]) return n;
        n=pt[n].link;
    }
    return n;
}
void extend(char s[],int i)
{
    int n=find(last,s,i);
    if(pt[n].to.count(s[i])==0){
        int m=size++;
        init_node(m);
        pt[n].to[s[i]]=m;
        pt[m].len=pt[n].len+2;
        if(pt[m].len==1) pt[m].link=1;
        else{
            int v=find(pt[n].link,s,i);
            pt[m].link=pt[v].to[s[i]];
        }
        last=m;
    }
    else last=pt[n].to[s[i]];
}
int main()
{
    scanf("%s",s);
    int n=strlen(s);
    init_pt();
    for(int i=0;i<n;i++){
        extend(s,i);
        pt[last].cnt++;
        if(vis[last]) continue;
        vis[last]=true;
        idx[pt[last].len].push_back(last);
    }
    for(int i=n;i>0;i--){
        int l=idx[i].size();
        for(int j=0;j<l;j++){
            int v=idx[i][j];
            int u=pt[v].link;
            if(u>1) pt[u].cnt+=pt[v].cnt;
        }
    }
    ll ans=0;
    for(int i=2;i<size;i++){
        ans=max(ans,(ll)pt[i].cnt*(ll)pt[i].len);
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s);
     ~~~~~^~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27