Submission #231286

#	Time	Username	Problem	Language	Result	Execution time	Memory
231286		lyc	Palindromes (APIO14_palindrome)	C++14	73 / 100	164 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;
const int A = 26+3;

struct trie {
    int nex[mxN][A], pa[mxN][lgN], v[mxN], cnt;

    trie() {
        memset(nex,-1,sizeof nex);
        cnt = 1;
        v[0] = 0;
        FOR(k,0,lgN-1) pa[0][k] = -1;
    }

    int make(int fa) {
        int u = cnt++;
        v[u] = 0;
        pa[u][0] = fa;
        FOR(k,1,lgN-1) pa[u][k] = (pa[u][k-1] == -1 ? -1 : pa[pa[u][k-1]][k-1]);
        return u;
    }

    int nthPa(int u, int n) {
        RFOR(k,lgN-1,0) if (n&(1<<k)) {
            if (u == -1) break;
            else u = pa[u][k];
        }
        return u;
    }

    int get(int u, char c) {
        if (nex[u][c-'a'] == -1) {
            nex[u][c-'a'] = make(u);
        }
        return nex[u][c-'a'];
    }

    ll ans(int u, int d) {
        //TRACE(d _ v);
        ll r = 0;
        FOR(i,0,A-1) if (nex[u][i] != -1) {
            r = max(r, ans(nex[u][i],d+1));
            v[u] += v[nex[u][i]];
        }
        r = max(r, (ll)d*v[u]);
        return r;
    }
} root;

int cur[mxN];

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);

    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] = root.nthPa(cur[_i],P[_i]-P[i]);
        } else {
            cur[i] = root.get(0,T[i]);
        }
        while (T[i+P[i]+1] == T[i-P[i]-1]) {
            cur[i] = root.get(cur[i],T[i+P[i]+1]);
            ++P[i];
        }
        ++root.v[cur[i]];
        if (i+P[i] > r) m = i, r = i+P[i];
    }
    cout << root.ans(0,-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