Submission #831498

#	Time	Username	Problem	Language	Result	Execution time	Memory
831498		Koyote	Palindromes (APIO14_palindrome)	C++14	100 / 100	94 ms	81040 KiB

palindrome

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

struct palin_tree {
    struct node {
        int len, suff_edge, serial_link = 0, diff = 0, occ = 0;
        vector<int> edges;
        map<char, int> nxt; // use this if n <= 1e6 and memory <= 256MB
        node(int _len = 0, int _suff_edge = 0) : len(_len), suff_edge(_suff_edge) {}
    };

    vector<node> tree;
    vector<char> past;
    int turtle;

    palin_tree(int expected_size = int(1e6)) : tree(2, node()), past(1, -1) {
        tree.reserve(expected_size), past.reserve(expected_size);
        tree[0].suff_edge = 1, tree[1].len = -1;
        turtle = 0;
        tree[1].edges.push_back(0);
    }

    int go_back(int u) {
        while (past[(int)past.size() - tree[u].len - 2] != past.back()) 
            u = tree[u].suff_edge;
        return u;
    }

    void append(int c) {
        past.push_back(c);
        turtle = go_back(turtle);
        if (!tree[turtle].nxt[c]) {
            node tmp; tmp.len = tree[turtle].len + 2;
            tmp.suff_edge = tree[go_back(tree[turtle].suff_edge)].nxt[c];
            tmp.diff = tmp.len - tree[tmp.suff_edge].len;
            tmp.serial_link = (tmp.diff != tree[tmp.suff_edge].diff ?
                tmp.suff_edge : tree[tmp.suff_edge].serial_link);
            
            tree[turtle].nxt[c] = (int)tree.size();
            tree[tmp.suff_edge].edges.push_back((int)tree.size());
            tree.push_back(tmp);
        }
        turtle = tree[turtle].nxt[c];
        tree[turtle].occ++;
    }

    long long solve(int u = 1) {
        long long res = 0;
        for (int v : tree[u].edges) {
            res = max(res, solve(v));
            tree[u].occ += tree[v].occ;
        }
        return max(res, 1LL * tree[u].occ * tree[u].len);
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string s; s.reserve(int(3e5)); cin >> s;
    palin_tree ptree(s.size());
    for (auto c : s) ptree.append(c - 'a');
    cout << ptree.solve() << '\n';
}

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