/*
______ _____ _______ _ _ _______ __ _ _____ _ _ _
|_____/ | | | |____/ |______ | \ | | | | | |
| \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__|
. . . . . .
_\/ \/_ _\/ \/_ _\/ \/_
_\/\/_ _\/\/_ _\/\/_
_\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_
/ /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \
_/\/\_ _/\/\_ _/\/\_
/\ /\ /\ /\ /\ /\
' ' ' ' ' '
*/
#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{
struct node {
int head; /**< The path-label start at &(Ti[head]) */
int sdep; /**< String-Depth, from the root down to node */
node* child; /**< First child */
node* brother; /**< Brother */
node* slink; /**< Suffix-Link */
node** hook; /**< What keeps this node linked? */
};
int a;
node* A;
int ptr2loc(node* v, node* x){
int r;
r = -1;
if(NULL != v) r = ((size_t) v - (size_t) x) / sizeof(struct node);
return (int)r;
}
void shownode(node* v) {
if(NULL == v){
printf("NULL\n");
}else{
printf("node: %d ", ptr2loc(v, A));
printf("head: %d ", v->head);
printf("sdep: %d ", v->sdep);
printf("child: %d ", ptr2loc(v->child, A));
printf("brother: %d ", ptr2loc(v->brother, A));
printf("slink: %d", ptr2loc(v->slink, A));
printf("\n");
}
}
struct point {
node* a; /**< node above */
node* b; /**< node bellow */
int s; /**< String-Depth */
};
int n;
string T;
int DescendQ(point* p, char c){
if(p->s==-1) return 1; /* sentinel */
else if(p->a==p->b){
/* look for next node */
node* y=p->b->child;
while(y!=NULL && T[y->head+p->s]!=c) y=y->brother;
if(y==NULL) return 0;
else return 1;
}else{
/*descend on edge*/
if(T[p->b->head+p->s]==c) return 1;
else return 0;
}
}
void Descend(point* p, char c){
if(p->s==-1){
/* sentinel */
p->a=&A[0];
p->b=&A[0];
p->s=0;
}else if(p->b->sdep==p->s){
/* look for next node */
node* y=p->b->child;
while(y!=NULL && T[y->head+p->s]!=c) y=y->brother;
p->a=p->b;
p->b=y;
p->s++;
if(p->s==p->b->sdep) p->a=p->b;
}else{
/*descend on edge*/
p->s++;
if(p->s==p->b->sdep) p->a=p->b;
}
}
void add_connection(node* u, node* v){
/* connect v as child of u */
if(u->child==NULL){
u->child=v;
v->hook=&(u->child);
}else{
v->brother=u->child;
u->child->hook=&(v->brother);
u->child=v;
v->hook=&(u->child);
}
}
void split(node* u, node* v, int s){
/* split edge to node u with sdep s and add node v at this position*/
v->head=u->head;
v->sdep=s;
if(u->brother!=NULL){
v->brother=u->brother;
u->brother->hook=&(v->brother);
}else{
v->brother=NULL;
}
u->brother=NULL;
v->child=u;
*(u->hook)=v;
v->hook=u->hook;
u->hook=&(v->child);
}
node* last;
int AddLeaf(point* p, int i){
if(p->b==p->a){
/* add leaf */
A[a].sdep=n-i+p->s;
A[a].head=i-p->s;
add_connection(p->b, &A[a]);
//printf("Leaf ");
//shownode(&A[a]);
return 1;
}else{
/* split */
split(p->b, &A[a], p->s);
//printf("Internal ");
//shownode(&A[a]);
last=&A[a];
/* add leaf */
A[a+1].sdep=n-i+p->s;
A[a+1].head=i-p->s;
add_connection(&A[a], &A[a+1]);
//printf("Leaf ");
//shownode(&A[a+1]);
return 2;
}
}
void SuffixLink(point* p){
/*printf("Begin SL a: %d b: %d s: %d\n",
ptr2loc(p->a, A), ptr2loc(p->b, A), p->s);*/
node* cur, *y;
int s, head;
cur=p->a->slink;
s=p->s-1;
head=p->b->head;
p->a=cur;
p->b=cur;
p->s=cur->sdep;
while(p->s<s){
/*
printf("a: %d\n",ptr2loc(p->a, A));
printf("b: %d\n",ptr2loc(p->b, A));
printf("s: %d\n",p->s);*/
if(p->b==&A[1]){ /* sentinel */
p->a=p->b=&A[0];
p->s=0;
}else{
y=p->b->child;
while(y!=NULL && T[y->head+p->s]!=T[head+p->s+1]) y=y->brother;
if(y->sdep<=s){
p->a=p->b=y;
p->s=y->sdep;
}else{
p->b=y;
p->s=s;
}
}
}
if(last!=NULL){
if(p->a==p->b){
last->slink=p->a;
}else last->slink=&A[a];
last=NULL;
}
/*printf("End SL a: %d b: %d s: %d\n",
ptr2loc(p->a, A), ptr2loc(p->b, A), p->s);*/
}
SuffixTree(string str){
int i;
point* p=(point*)malloc(sizeof(struct point));
T=str;
n=T.size();
A=(node*)calloc(MX, sizeof(struct node));
p->a=&A[0];
p->b=&A[0];
p->s=0;
/* root */
A[0].head=0;
A[0].sdep=0;
A[0].slink=&A[1];
A[0].hook=&A[1].child;
/* sentinel */
A[1].head=0;
A[1].sdep=-1;
A[1].child=&A[0];
a=2;
i=0;
last=NULL;
while(i<n){
while(!DescendQ(p, T[i])){
a+=AddLeaf(p, i);
SuffixLink(p);
}
Descend(p, T[i]);
i++;
}
free(p);
}
~SuffixTree(){
free(A);
}
};
void caso_teste(){
string str; cin>>str;
int n=str.size();
string rev=str;
reverse(all(rev));
str+=((char)('a'+26));
str+=rev;
str+=((char)('a'+27));
SuffixTree st(str);
vector<set<int>> vv(MX);
vector<int> count(MX, 0);
int cur=0;
auto dfs = [&](auto&& self, int s, int par) -> void {
int leaf=0;
if(st.A[s].child==NULL) leaf=1;
if(leaf){
//assert(str[st.r[s]-1]==((char)('a'+27)));
int k=st.A[s].sdep;
if(k!=1 && k!=n+2){
if(k<n+2) k-=2;
else k-=(n+3), k=n-k-1-par;
vv[s].insert(k);
}
}else{
SuffixTree::node* y=st.A[s].child;
while(y!=NULL){
//str_depth[y]=str_depth[s]+st.r[y]-st.l[y];
int yi=st.ptr2loc(y, st.A);
self(self, yi, par);
count[s]+=count[yi];
if(vv[yi].size()>vv[s].size()) swap(vv[yi], vv[s]);
for(int u: vv[yi]){
if(vv[s].find(u)!=vv[s].end()) vv[s].erase(u), count[s]++;
else vv[s].insert(u);
}
y=y->brother;
}
}
//cout<<s<<' '<<leaf<<' '<<count[s]<<' '<<st.A[s].sdep<<endl;
cur=max(cur, count[s]*(2*st.A[s].sdep-(1-par)));
};
dfs(dfs, 0, 0);
vv.assign(MX, set<int>());
count.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 |
Correct |
26 ms |
61532 KB |
Output is correct |
| 2 |
Correct |
20 ms |
61528 KB |
Output is correct |
| 3 |
Correct |
21 ms |
61532 KB |
Output is correct |
| 4 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 5 |
Correct |
22 ms |
61532 KB |
Output is correct |
| 6 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 7 |
Correct |
19 ms |
61532 KB |
Output is correct |
| 8 |
Correct |
19 ms |
61544 KB |
Output is correct |
| 9 |
Correct |
19 ms |
61532 KB |
Output is correct |
| 10 |
Correct |
21 ms |
61532 KB |
Output is correct |
| 11 |
Correct |
21 ms |
61536 KB |
Output is correct |
| 12 |
Correct |
21 ms |
61528 KB |
Output is correct |
| 13 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 14 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 15 |
Correct |
21 ms |
61780 KB |
Output is correct |
| 16 |
Correct |
19 ms |
61372 KB |
Output is correct |
| 17 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 18 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 19 |
Correct |
19 ms |
61384 KB |
Output is correct |
| 20 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 21 |
Correct |
19 ms |
61560 KB |
Output is correct |
| 22 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 23 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 24 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 25 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 26 |
Correct |
20 ms |
61532 KB |
Output is correct |
| 27 |
Correct |
21 ms |
61532 KB |
Output is correct |
| 28 |
Correct |
20 ms |
61528 KB |
Output is correct |
| 29 |
Correct |
19 ms |
61532 KB |
Output is correct |
| 30 |
Correct |
19 ms |
61528 KB |
Output is correct |
| 31 |
Correct |
19 ms |
61528 KB |
Output is correct |
| 32 |
Correct |
20 ms |
61572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
61788 KB |
Output is correct |
| 2 |
Correct |
20 ms |
61836 KB |
Output is correct |
| 3 |
Correct |
21 ms |
61784 KB |
Output is correct |
| 4 |
Correct |
21 ms |
61788 KB |
Output is correct |
| 5 |
Correct |
22 ms |
61912 KB |
Output is correct |
| 6 |
Correct |
20 ms |
61788 KB |
Output is correct |
| 7 |
Correct |
23 ms |
62044 KB |
Output is correct |
| 8 |
Correct |
21 ms |
61784 KB |
Output is correct |
| 9 |
Correct |
23 ms |
61788 KB |
Output is correct |
| 10 |
Correct |
25 ms |
61804 KB |
Output is correct |
| 11 |
Correct |
23 ms |
61788 KB |
Output is correct |
| 12 |
Correct |
22 ms |
62044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
67240 KB |
Output is correct |
| 2 |
Correct |
32 ms |
64852 KB |
Output is correct |
| 3 |
Correct |
34 ms |
65372 KB |
Output is correct |
| 4 |
Correct |
32 ms |
64884 KB |
Output is correct |
| 5 |
Correct |
60 ms |
70428 KB |
Output is correct |
| 6 |
Correct |
51 ms |
67624 KB |
Output is correct |
| 7 |
Correct |
36 ms |
65904 KB |
Output is correct |
| 8 |
Correct |
51 ms |
65636 KB |
Output is correct |
| 9 |
Correct |
46 ms |
67412 KB |
Output is correct |
| 10 |
Correct |
63 ms |
68948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
106496 KB |
Output is correct |
| 2 |
Correct |
166 ms |
100956 KB |
Output is correct |
| 3 |
Incorrect |
153 ms |
101476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
83 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
