Submission #422041

#	Time	Username	Problem	Language	Result	Execution time	Memory
422041		cpp219	Palindromes (APIO14_palindrome)	C++14	100 / 100	102 ms	104112 KiB

palindrome

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 3e5 + 9;
const ll mod = 1e9 + 7;
typedef pair<ll,ll> LL;

struct node{
    ll nxt[26];
    ll len;
    ll sufflink;
    ll num; vector<ll> g;
};
ll ans = 1;
ll now;
ll suff;

node tree[N];

void Init(){
    now = 2; suff = 2;
    tree[1].len = -1; tree[1].sufflink = 1; tree[1].g.push_back(2);
    tree[2].len = 0; tree[2].sufflink = 1;
}
string s;
void Add(ll pos){
    ll c = s[pos] - 'a';
    ll cur = suff,curlen = 0;
    while(1){
        curlen = tree[cur].len;
        if (pos - 1 - curlen >= 0 && s[pos] == s[pos - 1 - curlen]) break;
        cur = tree[cur].sufflink;
    }

    if (tree[cur].nxt[c]){
        suff = tree[cur].nxt[c];
        tree[suff].num++;
        return;
    }

    now++; suff = now;
    tree[now].len = tree[cur].len + 2;
    tree[cur].nxt[c] = now; tree[now].num = 1;
    if (tree[now].len == 1){
        tree[now].sufflink = 2;
        tree[2].g.push_back(now);
        return;
    }

    while(1){
        cur = tree[cur].sufflink;
        curlen = tree[cur].len;
        if (pos - 1 - curlen >= 0 && s[pos] == s[pos - 1 - curlen]) break;
    }
    tree[now].sufflink = tree[cur].nxt[c];
    tree[tree[now].sufflink].g.push_back(now);

}

void DFS(ll u){
    for (auto i : tree[u].g){
        DFS(i);
        tree[u].num += tree[i].num;
    }
    ans = max(ans,tree[u].num * tree[u].len);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>s; Init();
    for (ll i = 0;i < s.size();i++) Add(i);
    DFS(1);
    cout<<ans;
}

Compilation message (stderr)

palindrome.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
palindrome.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
palindrome.cpp: In function 'int main()':
palindrome.cpp:84:21: 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]
   84 |     for (ll i = 0;i < s.size();i++) Add(i);
      |                   ~~^~~~~~~~~~
palindrome.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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