Submission #231276

#	Time	Username	Problem	Language	Result	Execution time	Memory
231276		lyc	Palindromes (APIO14_palindrome)	C++14	73 / 100	268 ms	131076 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 600010;
const int lgN = 20;

struct node {
    node* pa[lgN];
    map<char,node*> child;
    int v;

    node(node* fa): v(0) {
        pa[0] = fa;
        FOR(k,1,lgN-1) pa[k] = (pa[k-1] != NULL ? pa[k-1]->pa[k-1] : NULL);
        //FOR(i,0,A-1) child[i] = NULL;
    }

    node* nthPa(int n) {
        node* r = this;
        RFOR(k,lgN-1,0) if (n&(1<<k)) {
            if (r != NULL) r = r->pa[k];
        }
        return r;
    }

    node* get(char c) {
        if (!child.count(c-'a')) {
            child[c-'a'] = new node(this);
        }
        return child[c-'a'];
    }

    void add(int x) { v += x; }

    ll ans(int d) {
        //TRACE(d _ v);
        ll r = 0;
        for (auto& c : child) {
            r = max(r, c.second->ans(d+1));
            v += c.second->v;
        }
        r = max(r, (ll)d*v);
        return r;
    }

    void dbg(string S, int d) {
        TRACE(S _ "::" _ d _ v);
        for (auto& c : child) {
            c.second->dbg(S + c.first, d+1);
        }
    }
} *cur[mxN], *root;

string S, T;
int N, P[mxN];

string preprocess(string S) {
    string T = "{";
    for (auto& c : S) {
        T += "|";
        T += c;
    }
    T += "|}";
    return T;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> S;
    T = preprocess(S);
    N = SZ(T);

    root = new node(NULL);
    int m = 0, r = 0;
    fill_n(P,N,0);
    FOR(i,1,N-2){
        int _i = m - (i-m);
        if (r > i) {
            P[i] = min(P[_i], r-i);
            cur[i] = cur[_i]->nthPa(P[_i]-P[i]);
        } else {
            cur[i] = root->get(T[i]);
        }
        while (T[i+P[i]+1] == T[i-P[i]-1]) {
            cur[i] = cur[i]->get(T[i+P[i]+1]);
            ++P[i];
        }
        cur[i]->add(1);
        if (i+P[i] > r) m = i, r = i+P[i];
    }
    cout << root->ans(-1) << '\n';
    //cout << T << '\n';
    //FOR(i,0,N-1) cout << P[i] << ' ';
    //cout << endl;
    //root->dbg("",-1);
}

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