Submission #253632

#	Time	Username	Problem	Language	Result	Execution time	Memory
253632		dolphingarlic	Palindromes (APIO14_palindrome)	C++14	100 / 100	69 ms	69628 KiB

palindrome

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    int nxt[26], sufflink;
    ll len, cnt;
    vector<int> edges;
} tree[303030];

string s;
int suff, num;
ll ans = 0;

void add_letter(int pos) {
    int curr = suff, curr_len = 0;
    int letter = s[pos] - 'a';

    while (true) {
        curr_len = tree[curr].len;
        if (pos - 1 - curr_len > -1 && s[pos - 1 - curr_len] == s[pos])
            break;
        curr = tree[curr].sufflink;
    }
    if (tree[curr].nxt[letter]) {
        suff = tree[curr].nxt[letter];
        tree[suff].cnt++;
        return;
    }
    
    suff = ++num;
    tree[num].len = tree[curr].len + 2;
    tree[num].cnt = 1;
    tree[curr].nxt[letter] = num;

    if (tree[num].len == 1) {
        tree[num].sufflink = 2;
        tree[2].edges.push_back(num);
        return;
    }

    while (true) {
        curr = tree[curr].sufflink;
        curr_len = tree[curr].len;
        if (pos - 1 - curr_len > -1 && s[pos - 1 - curr_len] == s[pos]) {
            tree[num].sufflink = tree[curr].nxt[letter];
            tree[tree[curr].nxt[letter]].edges.push_back(num);
            break;
        }
    }
}

void init() {
    num = 2, suff = 2;
    tree[1].len = -1, tree[1].sufflink = 1;
    tree[2].len = 0, tree[2].sufflink = 1;
    tree[1].edges.push_back(2);
}

void dfs(int node = 1) {
    for (int i : tree[node].edges) {
        dfs(i);
        tree[node].cnt += tree[i].cnt;
    }
    ans = max(ans, tree[node].len * tree[node].cnt);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    init();
    FOR(i, 0, s.size()) add_letter(i);
    dfs();
    cout << ans;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
palindrome.cpp:74:9:
     FOR(i, 0, s.size()) add_letter(i);
         ~~~~~~~~~~~~~~                  
palindrome.cpp:74:5: note: in expansion of macro 'FOR'
     FOR(i, 0, s.size()) add_letter(i);
     ^~~

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