Submission #745146

#	Time	Username	Problem	Language	Result	Execution time	Memory
745146		ACE_	Palindromes (APIO14_palindrome)	C++14	0 / 100	68 ms	87780 KiB

palindrome

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int cnt[N], in[N], last = 0, cur = 1;
struct eer {
    int e[26], suf, sz;
} t[N];
vector<int> V[N];
string s;
void add(int i) {
//    cout << t[cur].f << " " << t[cur].s << endl;
    while(true) {
        if(s[i] == s[i - t[last].sz - 1]) {
            if(t[last].e[s[i] - 'a']) {
                last = t[last].e[s[i] - 'a'];
                ++cnt[last];
                return;
            }
            t[last].e[s[i] - 'a'] = ++cur;
            t[cur].sz = t[last].sz + 2;
            cnt[cur] = 1;
            break;
        }
        last = t[last].suf;
    }
    int id = t[last].suf;
    last = cur;
    if(id == 0) {
        t[cur].suf = 1;
        return;
    }
    while(true) {
        if(s[i] == s[i - t[id].sz - 1]) {
            t[cur].suf = t[id].e[s[i] - 'a'];
            V[cur].push_back(t[id].e[s[i] - 'a']);
            ++in[t[id].e[s[i] - 'a']];
            return;

        }
        if(id == 0) {
            t[cur].suf = 1;
            return;
        }
        id = t[id].suf;
    }
}
main(){
    cin >> s;
    t[0].sz = -1;
    t[1].sz = 0;
    cur = 1; last = cur;
    for(int i = 0; i < s.size(); i++) {
        add(i);
    }
    queue<int> q;
    for(int i = 1; i <= cur; i++) {
        if(!in[i]) q.push(i);
    }
    int ans = 0;
    while(q.size()) {
        int x = q.front();
        q.pop();
        ans = max(ans, t[x].sz * cnt[x]);
        for(int i = 0; i < V[x].size(); i++) {
            cnt[V[x][i]] += cnt[x];
            --in[V[x][i]];
            if(!in[V[x][i]]) q.push(V[x][i]);
        }
    }
    cout << ans;

 }

Compilation message (stderr)

palindrome.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main(){
      | ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:53:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
palindrome.cpp:65:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < V[x].size(); i++) {
      |                        ~~^~~~~~~~~~~~~

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