/*
______ _____ _______ _ _ _______ __ _ _____ _ _ _
|_____/ | | | |____/ |______ | \ | | | | | |
| \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__|
. . . . . .
_\/ \/_ _\/ \/_ _\/ \/_
_\/\/_ _\/\/_ _\/\/_
_\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_
/ /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \
_/\/\_ _/\/\_ _/\/\_
/\ /\ /\ /\ /\ /\
' ' ' ' ' '
*/
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define f first
#define s second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
void banana(string nome=""){
cin.tie(0); ios_base::sync_with_stdio(0);
cout<<fixed<<setprecision(12);
if(nome.size()){
freopen((nome+".txt").c_str(),"r",stdin);
freopen((nome+"_in"+".txt").c_str(),"w",stdout);
}
}
string yon(ll ans){
return ans?"YES":"NO";
}
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
const int MX=1200010;
struct SuffixTree {
enum { N = MX, ALPHA = 28 }; // N ~ 2*maxlen+10
int toi(char c) { return c - 'a'; }
string a; // v = cur node, q = cur position
int t[N][ALPHA],l[N],r[N],p[N],s[N],v=0,q=0,m=2;
void ukkadd(int i, int c) {
suff:
if (r[v]<=q) {
if (t[v][c]==-1) { t[v][c]=m; l[m]=i;
p[m++]=v; v=s[v]; q=r[v]; goto suff; }
v=t[v][c]; q=l[v];
}
if (q==-1 || c==toi(a[q])) q++; else {
l[m+1]=i; p[m+1]=m; l[m]=l[v]; r[m]=q;
p[m]=p[v]; t[m][c]=m+1; t[m][toi(a[q])]=v;
l[v]=q; p[v]=m; t[p[m]][toi(a[l[m]])]=m;
v=s[p[m]]; q=l[m];
while (q<r[m]) { v=t[v][toi(a[q])]; q+=r[v]-l[v]; }
if (q==r[m]) s[m]=v; else s[m]=m+2;
q=r[v]-(q-r[m]); m+=2; goto suff;
}
}
SuffixTree(string a_) : a(a_) {
fill(r,r+N,sz(a));
memset(s, -1, sizeof s);
memset(t, -1, sizeof t);
fill(t[1],t[1]+ALPHA,0);
s[0] = 1; l[0] = l[1] = -1; r[0] = r[1] = p[0] = p[1] = 0;
rep(i,0,sz(a)) ukkadd(i, toi(a[i]));
}
};
void caso_teste(){
string str; cin>>str;
ll n=str.size();
string rev=str;
reverse(all(rev));
str+=((char)('a'+26));
str+=rev;
str+=((char)('a'+27));
SuffixTree st(str);
vector<set<ll>> v(MX);
vector<ll> count(MX, 0);
vector<ll> str_depth(MX, 0);
ll cur=0;
auto dfs = [&](auto&& self, ll s, ll par) -> void {
ll leaf=1;
for(ll i=0; i<28; i++) if(st.t[s][i]!=-1) leaf=0;
if(leaf){
assert(str[st.r[s]-1]==((char)('a'+27)));
ll k=str_depth[s];
if(k!=1 && k!=n+2){
if(k<n+2) k-=2;
else k-=(n+3), k=n-k-1-par;
v[s].insert(k);
}
}
for(ll i=0; i<28; i++){
if(st.t[s][i]!=-1){
ll y=st.t[s][i];
str_depth[y]=str_depth[s]+st.r[y]-st.l[y];
self(self, y, par);
count[s]+=count[y];
if(v[y].size()>v[s].size()) swap(v[y], v[s]);
for(ll u: v[y]){
if(v[s].find(u)!=v[s].end()) v[s].erase(u), count[s]++;
else v[s].insert(u);
}
}
}
cur=max(cur, count[s]*(2*str_depth[s]-(1-par)));
};
dfs(dfs, 0, 0);
v.assign(MX, set<ll>());
count.assign(MX, 0);
str_depth.assign(MX, 0);
dfs(dfs, 0, 1);
cout<<cur<<'\n';
}
int main(){
banana();
int n_casos=1; //cin>>n_casos;
while(n_casos--) caso_teste();
}
Compilation message
palindrome.cpp: In function 'void banana(std::string)':
palindrome.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((nome+".txt").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen((nome+"_in"+".txt").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
