Submission #1269952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269952		ptr_dipra	Palindromes (APIO14_palindrome)	C++20	0 / 100	0 ms	320 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define fast {ios_base::sync_with_stdio(false); cin.tie(0);}
typedef long long ll;
#define int long long
#define float long double
class eertree{
public:
    //string must be 1 indexed
    vector<vector<int>> tree;
    int n, t, idx;
    vector<int> len, link, cnt;
    eertree(int sz){
        n=sz;
        len.resize(n+5);
        link.resize(n+5);
        tree.resize(n+5, vector<int>(26,0));
        cnt.resize(n+5,0);
        t=idx=2;
        len[1]=-1, len[2]=0;
        link[1]=link[2]=1;
    }
    void extend(string &s, int p)
    {
        while(s[p-len[t]-1]!=s[p]) t=link[t];
        int x=link[t];
        while(s[p-len[x]-1]!=s[p]) x=link[x];
        int c=s[p]-'a';
        if(!tree[t][c])
        {
            tree[t][c]=++idx;
            len[idx]=len[t]+2;
            link[idx]=(len[idx]==1?2:tree[x][c]);
        }
        t=tree[t][c];
        cnt[t]++;
    }
};
signed main()
{
    fast
    string s;
    cin >> s;
    eertree tr(s.size());
    s="@"+s;
    for(int i=1;i<s.size();i++) tr.extend(s,i);
    int ans=0;
    for(int i=tr.idx;i>2;i--) tr.cnt[tr.link[i]]+=tr.cnt[i];
    for(int i=3;i<=tr.idx;i++) ans+=tr.cnt[i]*tr.len[i];
    cout <<ans << '\n';
    return 0;
}

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