Submission #1218190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218190		Szymon_Pilipczuk	Palindromes (APIO14_palindrome)	C++20	100 / 100	97 ms	45640 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<vector<int>> tr;
int l(char c)
{
    return int(c) - int('a');
}
int main()
{
    tr.resize(2);
    tr[0].resize(29);
    tr[1].resize(29);
    rep(i,26)
    {
        tr[0][i] = -1;
        tr[1][i] = -1;
    }
    tr[0][26] = 0;
    tr[0][27] = -1;
    tr[1][26] = 0;
    tr[1][27] = 0;
    tr[0][28] = 0;
    tr[1][28] = 0;
    int cu = 1;
    string s;
    cin>>s;
    rep(i,s.size())
    {
        int c = l(s[i]);
        while(i-tr[cu][27]-1 < 0 || l(s[i-tr[cu][27]-1]) != c)
        {
            cu = tr[cu][26];
        }
       /* if(i == 3)
        {
            return 0;
        }*/
        if(tr[cu][c] == -1)
        {
            int cu2;
            if(cu != 0)
            {
                cu2 = tr[cu][26];
                while(i-tr[cu2][27]-1 < 0 || l(s[i-tr[cu2][27]-1]) != c)
                {
                    cu2 = tr[cu2][26];
                }
                cu2 = tr[cu2][c];
            }
            else
            {
                cu2 = 1;    
            }
           // cout<<cu<<" "<<cu2<<endl;
            tr[cu][c] = tr.size();
            vector<int> cc;
            rep(i,26)
            {
                cc.pb(-1);
            }
            cc.pb(cu2);
            cc.pb(tr[cu][27] + 2);
            cc.pb(1);
            tr.pb(cc);
            cu = tr[cu][c];
        }
        else
        {
            cu = tr[cu][c];
            tr[cu][28]++;
        }
       // cout<<i<<" "<<tr[cu][26]<<" "<<tr[cu][27]<<" "<<tr[cu][28]<<endl;

    }
    ll ans = 0;
    for(int i = tr.size()-1;i>=0;i--)
    {
        tr[tr[i][26]][28] += tr[i][28];
        ans = max(ans,(ll) tr[i][28] * tr[i][27]);
    }
    cout<<ans;
    
}

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