oj.uz

Submission #376242

# Submission time Handle Problem Language Result Execution time Memory
376242 2021-03-11T05:46:17 Z fishy15 Palindromes (APIO14_palindrome) C++17
0 / 100
 151 ms 22688 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <numeric>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 300010

using namespace std;

int n;
string s;
int d1[MAXN];
int d2[MAXN];
int sa[MAXN];

// used for suffix array
int classes[MAXN];
int old_sa[MAXN];
int old_c[MAXN];
int idx[MAXN];
int cnt[MAXN];

// used for lcp
int inv_sa[MAXN];
int lcp[MAXN];

ll ans;

struct DSU {
    int dsu[MAXN];
    int sz[MAXN];

    void reset() { 
        iota(dsu, dsu + n, 0);
        fill(sz, sz + n, 1);
    }

    int find(int x) {
        return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
    }

    void join(int x, int y) {
        if (((x = find(x)) != (y = find(y)))) {
            if (sz[x] < sz[y]) swap(x, y);
            dsu[y] = x;
            sz[x] += sz[y];
        }
    }
} dsu;

void manachers() {
    // odd length palindrome
    int l = 0;
    int r = -1;
    for (int i = 0; i < n; i++) {
        int k = 1;
        if (i <= r) k = min(d1[l + r - i], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k--;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }

    // even length palindrome
    l = 0;
    r = -1;
    for (int i = 0; i < n; i++) {
        int k = 0;
        if (i <= r) k= min(d1[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++;
        d2[i] = k--;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
}

void suffix_array() {
    for (int i = 0; i < n; i++) {
        sa[i] = n - i - 1;
        classes[i] = s[i];
    }
    stable_sort(sa, sa + n, [](int i, int j) { return s[i] < s[j]; });
    for (int len = 1; len < n; len *= 2) {
        copy(sa, sa + n, old_sa);
        copy(classes, classes + n, old_c);
        fill(idx, idx + n, 1);
        iota(cnt, cnt + n, 0);
        for (int i = 0; i < n; i++) {
            bool same = i && sa[i - 1] + len < n
                && old_c[sa[i]] == old_c[sa[i - 1]]
                && old_c[sa[i] + len / 2] == old_c[sa[i - 1] + len / 2];
            classes[sa[i]] = same ? classes[sa[i - 1]] : i;
        }
        for (int i = 0; i < n; i++) {
            int pos = sa[i] - len;
            if (pos >= 0) {
                sa[cnt[classes[pos]]++] = pos;
            }
        }
    }
}

void kasai() {
    int k = 0;
    for (int i = 0; i < n; i++) {
        inv_sa[sa[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        if (inv_sa[i] == n - 1) {
            k = 0;
        } else {
            int j = sa[inv_sa[i] + 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
            lcp[inv_sa[i]] = k;
            if (k) k--;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> s;
    n = s.size();

    manachers();
    suffix_array();
    kasai();

    for (int i = 0; i < n; i++) {
        ans = max<ll>(ans, 2 * d1[i] - 1);
        ans = max<ll>(ans, 2 * d2[i]);
    }

    dsu.reset();
    vector<array<int, 3>> ord;
    for (int i = 0; i < n - 1; i++) {
        ord.push_back({min({lcp[i], d1[sa[i]], d1[sa[i + 1]]}), i, i + 1});
    }

    sort(ord.rbegin(), ord.rend());
    for (auto [sz, pos1, pos2] : ord) {
        dsu.join(pos1, pos2);
        ans = max(ans, 1LL * (2 * sz - 1) * dsu.sz[dsu.find(pos1)]);
    }

    dsu.reset();
    ord.clear();
    for (int i = 0; i < n - 1; i++) {
        if (d2[sa[i]] == 0) continue;
        int nxt = i + 1;
        int common = lcp[i];
        while (common && nxt < n && d2[sa[nxt]] == 0) {
            nxt++;
            common = min(lcp[nxt], common);
        }
        if (nxt < n) ord.push_back({min({common, d2[sa[i]], d2[sa[nxt]]}), i, nxt});
    }

    sort(ord.rbegin(), ord.rend());
    for (auto [sz, pos1, pos2] : ord) {
        dsu.join(pos1, pos2);
        ans = max(ans, 2LL * sz * dsu.sz[dsu.find(pos1)]);
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Incorrect 1 ms 492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1260 KB Output is correct
2 Correct 4 ms 1260 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 6 ms 1260 KB Output is correct
5 Incorrect 5 ms 1260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7048 KB Output is correct
2 Correct 42 ms 7048 KB Output is correct
3 Correct 66 ms 7040 KB Output is correct
4 Correct 57 ms 7048 KB Output is correct
5 Incorrect 51 ms 7048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 22688 KB Output is correct
2 Incorrect 151 ms 22176 KB Output isn't correct
3 Halted 0 ms 0 KB -