oj.uz

Submission #396344

# Submission time Handle Problem Language Result Execution time Memory
396344 2021-04-29T19:53:43 Z abdzag Palindromes (APIO14_palindrome) C++17
100 / 100
 89 ms 71288 KB 
#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  300002
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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB Output is correct
2 Correct 23 ms 47212 KB Output is correct
3 Correct 24 ms 47284 KB Output is correct
4 Correct 24 ms 47188 KB Output is correct
5 Correct 23 ms 47192 KB Output is correct
6 Correct 23 ms 47180 KB Output is correct
7 Correct 24 ms 47180 KB Output is correct
8 Correct 22 ms 47180 KB Output is correct
9 Correct 23 ms 47216 KB Output is correct
10 Correct 23 ms 47224 KB Output is correct
11 Correct 24 ms 47232 KB Output is correct
12 Correct 24 ms 47180 KB Output is correct
13 Correct 24 ms 47292 KB Output is correct
14 Correct 23 ms 47180 KB Output is correct
15 Correct 24 ms 47264 KB Output is correct
16 Correct 24 ms 47268 KB Output is correct
17 Correct 24 ms 47180 KB Output is correct
18 Correct 22 ms 47208 KB Output is correct
19 Correct 24 ms 47180 KB Output is correct
20 Correct 23 ms 47180 KB Output is correct
21 Correct 23 ms 47252 KB Output is correct
22 Correct 23 ms 47284 KB Output is correct
23 Correct 25 ms 47180 KB Output is correct
24 Correct 24 ms 47204 KB Output is correct
25 Correct 24 ms 47172 KB Output is correct
26 Correct 23 ms 47180 KB Output is correct
27 Correct 23 ms 47180 KB Output is correct
28 Correct 24 ms 47244 KB Output is correct
29 Correct 24 ms 47188 KB Output is correct
30 Correct 24 ms 47176 KB Output is correct
31 Correct 24 ms 47192 KB Output is correct
32 Correct 23 ms 47288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 24 ms 47308 KB Output is correct
3 Correct 24 ms 47288 KB Output is correct
4 Correct 24 ms 47308 KB Output is correct
5 Correct 24 ms 47336 KB Output is correct
6 Correct 24 ms 47296 KB Output is correct
7 Correct 23 ms 47224 KB Output is correct
8 Correct 24 ms 47284 KB Output is correct
9 Correct 24 ms 47252 KB Output is correct
10 Correct 23 ms 47180 KB Output is correct
11 Correct 24 ms 47180 KB Output is correct
12 Correct 24 ms 47196 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47820 KB Output is correct
2 Correct 25 ms 47668 KB Output is correct
3 Correct 25 ms 48008 KB Output is correct
4 Correct 24 ms 47948 KB Output is correct
5 Correct 25 ms 47440 KB Output is correct
6 Correct 28 ms 47544 KB Output is correct
7 Correct 25 ms 47628 KB Output is correct
8 Correct 24 ms 47448 KB Output is correct
9 Correct 24 ms 47248 KB Output is correct
10 Correct 25 ms 47440 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 52892 KB Output is correct
2 Correct 36 ms 51928 KB Output is correct
3 Correct 38 ms 55244 KB Output is correct
4 Correct 39 ms 53588 KB Output is correct
5 Correct 42 ms 48964 KB Output is correct
6 Correct 34 ms 49468 KB Output is correct
7 Correct 35 ms 50512 KB Output is correct
8 Correct 26 ms 47568 KB Output is correct
9 Correct 29 ms 49272 KB Output is correct
10 Correct 37 ms 48724 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 63908 KB Output is correct
2 Correct 61 ms 59212 KB Output is correct
3 Correct 64 ms 71288 KB Output is correct
4 Correct 60 ms 62312 KB Output is correct
5 Correct 89 ms 53100 KB Output is correct
6 Correct 59 ms 58316 KB Output is correct
7 Correct 59 ms 56488 KB Output is correct
8 Correct 31 ms 48228 KB Output is correct
9 Correct 31 ms 48212 KB Output is correct
10 Correct 75 ms 52020 KB Output is correct
11 Correct 62 ms 59540 KB Output is correct
12 Correct 33 ms 49924 KB Output is correct