oj.uz

Submission #823358

# Submission time Handle Problem Language Result Execution time Memory
823358 2023-08-12T11:21:10 Z abhishek_saini Palindromes (APIO14_palindrome) C++17
100 / 100
 75 ms 87784 KB 
#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h> 
 
using namespace std;
long long mod = 1e9 + 7;
double EPS = 1e-12;
typedef long long int lld;
typedef pair<lld,lld> PA;
long double tick(){static clock_t oldt; clock_t newt=clock();
    long double diff=1.0L*(newt-oldt)/CLOCKS_PER_SEC; oldt = newt; return diff; }
#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repI(i,a,n) for(int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); --i)
#define repDI(i,a,n) for(int i = (a); i >= (n); --i)
inline lld sc() { lld a; scanf("%lld", &a); return a; }
inline int scd() { int a; scanf("%d", &a); return a; }
#define prL(a) printf("%lld\n",a)
#define prS(a) printf("%lld ",a)
#define prdL(a) printf("%d\n",a)
#define prdS(a) printf("%d ",a)
#define all(c) (c).begin(), (c).end()
#define sz(a) ((int)a.size())
#ifdef LOCAL_RUN
#define Error(x...) { cout << "(" << #x << ")" << " = ( "; printIt(x); }
#define errorpair(a) cout<<#a<<" = ( "<<((a).first)<<" , "<<((a).second)<<" )\n";
#else
#define Error(x...) 42
#define errorpair(a) 42
#endif
template <typename T1> void printIt(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void printIt(T1 t1, T2... t2) { cout << t1 << " , "; printIt(t2...); }
#define mset(a, v) memset(a, v, sizeof(a))
#define popcount __builtin_popcountll

#define lim 300010
#define lim2 200010
// unordered_map<lld,lld>::iterator it; // Ab :)
// std::ios::sync_with_stdio(false);

lld A[lim];

struct Node{
    int len;
    Node *suffixLink;
    vector<Node*> palinEdges;
    int freq = 0;
    Node(int len){
        this->len = len;
        this->suffixLink = nullptr;
        this->palinEdges.resize(26, nullptr);
        this->freq = 1;
    }
};
vector<Node*> AllNodes;

int main(){
    string S;
    cin >> S;
    Node *zero = new Node(0);
    Node *negOne = new Node(-1);
    zero->suffixLink = negOne;
    negOne->suffixLink = negOne;
    Node *last = zero;

    // Build the Eer Tree
    int n = S.size();
    for(int idx = 0; idx < n; ++idx) {
        while(true) {
            int curLen = last->len;
            if(idx - curLen - 1 >= 0 && S[idx] == S[idx - curLen - 1]) break;
            last = last->suffixLink;
        }
        if(last->palinEdges.at(S[idx] - 'a') != nullptr) {
            last = last->palinEdges.at(S[idx] - 'a');
            last->freq++;
            continue;
        }
        Node *newNode = new Node(last->len + 2);
        AllNodes.push_back(newNode);
        last->palinEdges.at(S[idx] - 'a') = newNode;
        // palinEdges computed
        // Error(idx, S[idx], newNode->len, last->len);

        if(last == negOne) {
            newNode->suffixLink = zero;
            last = newNode;
            continue;
        }
        // Compute suffix link
        last = last->suffixLink;
        while(true) {
            int curLen = last->len;
            if(idx - curLen - 1 >= 0 && S[idx] == S[idx - curLen - 1]) break;
            last = last->suffixLink;
        }
        // set to zero if no suffix palindrome found
        // Error(last->len, last->palinEdges.at(S[idx] - 'a')->len);
        newNode->suffixLink = last->palinEdges.at(S[idx] - 'a');
        // Error(newNode->suffixLink->len);
        last = newNode;
    }

    // Problem Specific Logic
    lld ans = 1;
    int sz = AllNodes.size();
    for(int idx = sz - 1; idx >= 0; --idx) {
        Node *cur = AllNodes[idx];
        ans = max(ans, 1LL * cur->freq * cur->len);
        cur->suffixLink->freq += cur->freq;
    }
    prL(ans);
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 304 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 304 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 444 KB Output is correct
10 Correct 0 ms 312 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3132 KB Output is correct
2 Correct 3 ms 3156 KB Output is correct
3 Correct 2 ms 3288 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 3 ms 3156 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 2260 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29380 KB Output is correct
2 Correct 27 ms 29440 KB Output is correct
3 Correct 19 ms 29372 KB Output is correct
4 Correct 20 ms 29448 KB Output is correct
5 Correct 23 ms 29460 KB Output is correct
6 Correct 17 ms 21568 KB Output is correct
7 Correct 22 ms 25012 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 6 ms 7220 KB Output is correct
10 Correct 16 ms 24956 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 87756 KB Output is correct
2 Correct 63 ms 87772 KB Output is correct
3 Correct 57 ms 87688 KB Output is correct
4 Correct 55 ms 87752 KB Output is correct
5 Correct 75 ms 87720 KB Output is correct
6 Correct 51 ms 78836 KB Output is correct
7 Correct 67 ms 73052 KB Output is correct
8 Correct 7 ms 1280 KB Output is correct
9 Correct 7 ms 1248 KB Output is correct
10 Correct 58 ms 71928 KB Output is correct
11 Correct 56 ms 87784 KB Output is correct
12 Correct 11 ms 9188 KB Output is correct