Submission #493461

#	Time	Username	Problem	Language	Result	Execution time	Memory
493461		FEDIKUS	Palindromes (APIO14_palindrome)	C++17	100 / 100	95 ms	119744 KiB

palindrome

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(ll i=s;i<f;i++)
#define fb(i,s,f) for(ll i=(s)-1;i>=f;i--)
#define ffi(i,s,f) for(ll i=s;i<=f;i++)
#define fbi(i,s,f) for(ll i=s;i>=f;i--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,ll) sort(a.begin(),a.end(),greater<ll>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef string str;

struct node{
    ll dje[26];
    ll be=0,cnt=0,len=0;
};

vector<node> pt;

node prazan;
ll tren;
string s;

void addletter(ll i){
    if(pt[tren].len==i) tren=pt[tren].be;
    while(s[i-pt[tren].len-1]!=s[i]){
        tren=pt[tren].be;
    }
    if(pt[tren].dje[s[i]-'a']==0){
        pt.push_back(prazan);
        pt[tren].dje[s[i]-'a']=pt.size()-1;
    }
    ll len=pt[tren].len+2;
    ll be=-1;
    ll ntren=tren;

    tren=pt[tren].dje[s[i]-'a'];
    pt[tren].len=len;
    pt[tren].cnt++;
    if(ntren==1){
        be=2;
        pt[tren].be=be;
    }else{
        ntren = pt[ntren].be;
        while(s[i-pt[ntren].len-1]!=s[i]){
            ntren=pt[ntren].be;
    }
        be=ntren;
        if(pt[be].dje[s[i]-'a']==0){
            pt.push_back(prazan);
            pt[be].dje[s[i]-'a']=pt.size()-1;
        }
        pt[tren].be=pt[be].dje[s[i]-'a'];
    }
}

void init(){
    pt.clear();
    pt.push_back(prazan);
    pt.push_back(prazan);
    pt.push_back(prazan);
    pt[1].len=-1;
    pt[1].be=1;
    pt[2].len=0;
    pt[2].be=1;
    tren=1;
}

void solve(){
	cin>>s;
	init();
	for(ll i=0;i<s.size();i++) addletter(i);
	for(ll i=(ll)pt.size()-1;i>=1;i--){
        pt[pt[i].be].cnt+=pt[i].cnt;
	}
	ll maxi=-1;
	for(ll i=1;i<pt.size();i++){
        maxi=max(maxi,pt[i].cnt*pt[i].len);
	}
	cout<<maxi;
}

int main(){
    ios;
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void solve()':
palindrome.cpp:89:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(ll i=0;i<s.size();i++) addletter(i);
      |             ~^~~~~~~~~
palindrome.cpp:94:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(ll i=1;i<pt.size();i++){
      |             ~^~~~~~~~~~

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