Submission #1111629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111629		simona1230	Palindromes (APIO14_palindrome)	C++17	100 / 100	87 ms	109028 KiB

palindrome

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

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

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

// curr e vyrhyt S kojto prodyljavame s tek bukva x xSx
void add(long long p)
{
    long long i=s[p]-'a';
    long long 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);
}

long long sz[300001],ans;

void dfs(long long i)
{
    //cout<<i<<endl;
    sz[i]=l[i].cnt;
    for(long long j=0;j<l[i].v.size();j++)
    {
        long long 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(long long i=0;i<s.size();i++)
        add(i);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

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

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