Submission #1111628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111628		simona1230	Palindromes (APIO14_palindrome)	C++17	47 / 100	38 ms	63004 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

struct letter
{
    int l[27],suf,len,cnt;
    vector<int> v;
};

string s;
letter l[300001];
int last,num;

// curr e vyrhyt S kojto prodyljavame s tek bukva x xSx
void add(int p)
{
    int i=s[p]-'a';
    int curr=last,len=0;
    while(1)
    {
        len=l[curr].len;
        if(p-len-1>=0&&s[p-len-1]==s[p])
            break;

        curr=l[curr].suf;
    }

    if(l[curr].l[i])
    {
        last=l[curr].l[i];
        l[last].cnt++;
        return;
    }

    last=++num;
    l[num].len=l[curr].len+2;
    l[num].cnt=1;
    l[curr].l[i]=num;

    if(l[num].len==1)
    {
        l[num].suf=2;
        l[2].v.push_back(num);
        return;
    }

    while(1)
    {
        curr=l[curr].suf;
        len=l[curr].len;

        if(p-len-1>=0&&s[p-len-1]==s[p])
        {
            l[num].suf=l[curr].l[i];
            l[l[num].suf].v.push_back(num);
            break;
        }
    }
}

void init()
{
    num=2;
    last=2;
    l[1].len=-1;
    l[1].suf=1;

    l[2].len=0;
    l[2].suf=1;

    l[1].v.push_back(2);
}

int sz[300001],ans;

void dfs(int i)
{
    //cout<<i<<endl;
    sz[i]=l[i].cnt;
    for(int j=0;j<l[i].v.size();j++)
    {
        int nb=l[i].v[j];
        dfs(nb);

        sz[i]+=sz[nb];
    }

    ans=max(ans,sz[i]*l[i].len);
}


int main()
{
    cin>>s;
    init();
    for(int i=0;i<s.size();i++)
        add(i);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void dfs(int)':
palindrome.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int j=0;j<l[i].v.size();j++)
      |                 ~^~~~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~

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