Submission #375760

#	Time	Username	Problem	Language	Result	Execution time	Memory
375760		mohamedsobhi777	Palindromes (APIO14_palindrome)	C++14	100 / 100	116 ms	60740 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 1e6 + 7;
const ll mod = 1e9 + 7;

int n;
double dp[N];
double prefdp[N];
int suff;

struct node
{
        int nxt[26];
        int link = -1;
        int len = 0;
        int cnt = 0;
        node()
        {
                memset(nxt, 0, sizeof nxt);
        }
        int &operator[](int x)
        {
                return nxt[x];
        }
};

vector<node> eer;
string st;

bool extend(int pos)
{
        int cur = suff;

        while (1)
        {
                if (pos - eer[cur].len - 1 >= 0 && st[pos] == st[pos - eer[cur].len - 1])
                        break;
                cur = eer[cur].link;
        }

        if (eer[cur][st[pos] - 'a'])
        {
                suff = eer[cur][st[pos] - 'a'];
                eer[suff].cnt++;
                return 0;
        }
        suff = sz(eer);
        eer.push_back(node());
        eer[cur][st[pos] - 'a'] = suff;
        eer[suff].len = 2 + eer[cur].len;
        eer[suff].cnt ++ ; 
        if (eer[suff].len == 1)
        {
                eer[suff].link = 1;
                return 1;
        }

        while (true)
        {
                cur = eer[cur].link;
                if (st[pos] == st[pos - eer[cur].len - 1])
                {
                        eer[suff].link = eer[cur][st[pos] - 'a'];
                        break;
                }
        }

        return 1;
}

void process()
{
        eer.clear();
        eer.push_back(node());
        eer.push_back(node());
        eer[0].link = eer[1].link = 0;
        eer[0].len = -1, eer[1].len = 0;
        suff = 1;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
#ifndef ONLINE_JUDGE

#endif
        process();
        cin >> st;
        n = sz(st);
        for (int i = 0; i < n; ++i)
                extend(i);
        ll ans = 0;

        priority_queue<pii> pq;
        for (int i = 2; i < sz(eer); ++i)
        {
                pq.push({eer[i].len, i});
        }
        while (sz(pq))
        {
                pii tp = pq.top();
                pq.pop();
                eer[eer[tp.s].link].cnt += eer[tp.s].cnt;
        }
        for (int i = 1; i < sz(eer); ++i)
        {
                ans = max(ans, 1ll * eer[i].len * eer[i].cnt);
        }
        cout << ans;
        return 0;
}

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