Submission #493438

#	Time	Username	Problem	Language	Result	Execution time	Memory
493438		FEDIKUS	회문 (APIO14_palindrome)	C++17	0 / 100	25 ms	30528 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(int i=s;i<f;i++)
#define fb(i,s,f) for(int i=(s)-1;i>=f;i--)
#define ffi(i,s,f) for(int i=s;i<=f;i++)
#define fbi(i,s,f) for(int i=s;i>=f;i--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#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<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

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

vector<node> pt;

node prazan;
int tren;
string s;


void addletter(int i){
    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;
    }
    int len=pt[tren].len+2;
    int be=-1;
    int ntren=ntren=pt[tren].be;
    while(s[i-pt[ntren].len-1]!=s[i]){
        ntren=pt[ntren].be;
    }
    if(ntren==1){
        be=2;
    }else{
        be=ntren;
    }
    tren=pt[tren].dje[s[i]-'a'];
    pt[tren].len=len;
    pt[tren].cnt++;
    pt[tren].be=be;
}

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(int i=0;i<s.size();i++) addletter(i);
	for(int i=(int)pt.size()-1;i>=1;i--){
        pt[pt[i].be].cnt+=pt[i].cnt;
	}
	int maxi=-1;
	for(int i=1;i<pt.size();i++){
        maxi=max(maxi,pt[i].cnt*pt[i].len);
	}
	cout<<maxi;
}

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

Compilation message (stderr)

palindrome.cpp: In function 'void addletter(int)':
palindrome.cpp:52:20: warning: operation on 'ntren' may be undefined [-Wsequence-point]
   52 |     int ntren=ntren=pt[tren].be;
      |               ~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'void solve()':
palindrome.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<s.size();i++) addletter(i);
      |              ~^~~~~~~~~
palindrome.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i=1;i<pt.size();i++){
      |              ~^~~~~~~~~~

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