Submission #34030

#	Time	Username	Problem	Language	Result	Execution time	Memory
34030		nickyrio	Palindromes (APIO14_palindrome)	C++14	73 / 100	23 ms	21848 KiB

palindrome

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 100100
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
template<typename T> inline void read(T &x) {
    char c;
    while (!isdigit(c = getchar()));
    x = 0;
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
}
template<typename T> inline void write(T x) {
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

struct Node {
    int next[26];
    int suff, len, cnt;
};

struct PalindromicTree {
    vector<Node> tree;
    int n, currNode, ptr;
    string st;
    vector<vector<int> > e;
    void reset(string st) {
        n = st.size();
        this -> st = st;
        tree.resize(n + 3);
        e.resize(n + 3);
        currNode = 0;
        tree[0].len = -1;tree[0].suff = 0;
        tree[1].len = 0;tree[1].suff = 0;
        ptr = currNode = 1;
        REP(i, n) add(i);
    }

    long long getAns() {
        dfs(1);
        long long ans = 0;
        FOR(i, 2, ptr) {
            ans = max(ans, 1ll * tree[i].cnt * tree[i].len);
        }
        return ans;
    }
    void add(int pos) {
        int idx = st[pos] - 'a';
        int cur = currNode;
        while (true) {
            int curLen = tree[cur].len;
            if (pos - curLen >= 1 && st[pos] == st[pos - curLen - 1]) break;
            cur = tree[cur].suff;
        }
        if (tree[cur].next[idx]) {
            currNode = tree[cur].next[idx];
            tree[currNode].cnt++;
            return;
        }

        currNode = ++ptr;
        tree[cur].next[idx] = ptr;
        tree[ptr].cnt = 1;
        tree[ptr].len = tree[cur].len + 2;

        if (tree[ptr].len == 1) {
            tree[ptr].suff = 1;
            e[1].push_back(ptr);
            return;
        }

        cur = tree[cur].suff;
        while (true) {
            int curLen = tree[cur].len;
            if (pos - curLen >= 1 && st[pos] == st[pos - curLen - 1]) {
                tree[currNode].suff = tree[cur].next[idx];
                e[tree[cur].next[idx]].push_back(ptr);
                return;
            }
            cur = tree[cur].suff;
        }
    }
    void dfs(int u) {
        for (int v : e[u]) {
            dfs(v);
            tree[u].cnt += tree[v].cnt;
        }
    }
}PT;

char s[N];
string st;

int main() {
    IO;
    scanf("%s", s);
    string st = s;
    PT.reset(st);
    write(PT.getAns());
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:110:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
                   ^

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