Submission #396342

#	Time	Username	Problem	Language	Result	Execution time	Memory
396342		abdzag	Palindromes (APIO14_palindrome)	C++17	0 / 100	62 ms	131076 KiB

palindrome

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b); i--);
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)

using namespace std;

typedef long long ll;
#define MAXN  3000002
string s;

const ll inf = 1e15;
struct Node
{
    // store start and end indexes of current
    // Node inclusively
    int start, end;
    vector<ll> children;
    // stores length of substring
    int length;

    // stores insertion Node for all characters a-z
    int insertEdg[26];

    // stores the Maximum Palindromic Suffix Node for
    // the current Node
    int suffixEdg;

    int count;
};

// two special dummy Nodes as explained above
Node root1, root2;

// stores Node information for constant time access
Node tree[MAXN];

// Keeps track the current Node while insertion
int currNode;
int ptr;
void insert(int idx)
{
    //STEP 1//

        /* search for Node X such that s[idx] X S[idx]
           is maximum palindrome ending at position idx
           iterate down the suffix link of currNode to
           find X */
    int tmp = currNode;
    while (true)
    {
        int curLength = tree[tmp].length;
        if (idx - curLength >= 1 and s[idx] == s[idx - curLength - 1])
            break;
        tmp = tree[tmp].suffixEdg;
    }

    /* Now we have found X ....
     * X = string at Node tmp
     * Check : if s[idx] X s[idx] already exists or not*/
    if (tree[tmp].insertEdg[s[idx] - 'a'] != 0)
    {
        // s[idx] X s[idx] already exists in the tree
        currNode = tree[tmp].insertEdg[s[idx] - 'a'];
        tree[currNode].count++;
        return;
    }

    // creating new Node
    ptr++;

    // making new Node as child of X with
    // weight as s[idx]
    tree[tmp].insertEdg[s[idx] - 'a'] = ptr;

    // calculating length of new Node
    tree[ptr].length = tree[tmp].length + 2;

    // updating end point for new Node
    tree[ptr].end = idx;
    tree[ptr].count = 1;
    tree[ptr].start = idx - tree[ptr].length + 1;
    //STEP 2//

        /* Setting the suffix edge for the newly created
           Node tree[ptr]. Finding some String Y such that
           s[idx] + Y + s[idx] is longest possible
           palindromic suffix for newly created Node.*/

    tmp = tree[tmp].suffixEdg;

    // making new Node as current Node
    currNode = ptr;
    if (tree[currNode].length == 1)
    {
        // if new palindrome's length is 1
        // making its suffix link to be null string
        tree[currNode].suffixEdg = 2;
        return;
    }
    while (true)
    {
        int curLength = tree[tmp].length;
        if (idx - curLength >= 1 and s[idx] == s[idx - curLength - 1])
            break;
        tmp = tree[tmp].suffixEdg;
    }

    // Now we have found string Y
    // linking current Nodes suffix link with s[idx]+Y+s[idx]
    tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx] - 'a'];
    tree[tree[tmp].insertEdg[s[idx] - 'a']].children.push_back(currNode);
}
vector<ll> dp(3e5 + 2,-1);
ll howmany(ll cur) {
    if (dp[cur] != -1)return dp[cur];
    ll val = tree[cur].count;
    trav(a, tree[cur].children) val += howmany(a);
    return dp[cur] = val;
}
int main() {
    cin.sync_with_stdio(false);
    root1.length = -1;
    root1.suffixEdg = 1;
    root2.length = 0;
    root2.suffixEdg = 1;

    tree[1] = root1;
    tree[2] = root2;
    ptr = 2;
    currNode = 1;
    cin >> s;
    int l = s.size();
    rep(i, 0, l) insert(i);
    ll ans = 0;
    rep(i, 2, ptr + 1) {
        ll val = howmany(i)*tree[i].length;
        ans = max(ans, val);
    }
    cout << ans;
    return 0;
}

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