Submission #924869

#	Time	Username	Problem	Language	Result	Execution time	Memory
924869		arneves	Palindromes (APIO14_palindrome)	C++17	73 / 100	1065 ms	96616 KiB

palindrome

/*
           ______  _____  _______ _     _ _______ __   _  _____  _  _  _
          |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
          |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
        
        
                   .      .           .      .           .      .    
                   _\/  \/_           _\/  \/_           _\/  \/_    
                    _\/\/_             _\/\/_             _\/\/_     
                _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 
                 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  
                    _/\/\_             _/\/\_             _/\/\_     
                    /\  /\             /\  /\             /\  /\     
                   '      '           '      '           '      '    
        
*/

#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;
	ll n=str.size();
	string rev=str;
	reverse(all(rev));
	str+=((char)('a'+26));
	str+=rev;
	str+=((char)('a'+27));
	
	SuffixTree st(str);
	
	vector<int> vv(MX, -1);
	vector<set<int>> f;
	vector<int> livres;
	livres.reserve(5000);
	f.reserve(5000);
	
	vector<int> count(MX, 0);
	
	ll cur=0;
	
	auto novo=[&]() -> int {
		if(livres.size()){
			int ans=livres.back();
			livres.pop_back();
			f[ans].clear();
			return ans;
		}else{
			f.pb(set<int>());
			return f.size()-1;
		}
	};
	
	auto apagar=[&](int i) {
		f[i].clear();
		livres.pb(i);
	};
	
	vector<int> vis(MX, 0);
	
	auto work=[&](int par) -> void {
		
		vector<int> mem(MX, -1);
		mem[0]=0;
		int p=0, pp=0;
		
		while(p<=pp){
			int s=mem[p];
			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);
				pp++;
				mem[pp]=yi;
				y=y->brother;
			}
			p++;
		}
		
		p=pp;
		while(p>=0){
			int s=mem[p];
			vis[s]=1;
			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;
				vv[s]=novo();
				if(k!=1 && k!=n+2){
					if(k<n+2) k-=2;
					else k-=(n+3), k=n-k-1-par;
					f[vv[s]].insert(k);
				}
			}else{
				int sv=vv[s];
				if(sv==-1) vv[s]=novo();
				sv=vv[s];
				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);
					//assert(vis[yi]);
					count[s]+=count[yi];
					int yv=vv[yi];
					//if(yv==-1) vv[yi]=novo();
					//yv=vv[yi];
					//assert(yv!=-1);
					//assert(sv!=-1);
					if(f[yv].size()>f[sv].size()) swap(f[sv], f[yv]);
					
					for(int u: f[yv]){
						if(f[sv].count(u)==1) f[sv].erase(u), count[s]++;
						else f[sv].insert(u);
					}
					
					if(yv != -1) apagar(yv);
					vv[yi]=-1;
					y=y->brother;
				}
			}
			cur=max(cur, ((ll)count[s])*(2ll*((ll)st.A[s].sdep)-(1ll-par)));
			p--;
		}
	};
	
	/*
	auto dfs = [&](auto&& self, int s, ll 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].count(u)==1) vv[s].erase(u), count[s]++;
					else vv[s].insert(u);
				}
				
				vv[yi].clear();
				y=y->brother;
			}
		}
		//cout<<s<<' '<<leaf<<' '<<count[s]<<' '<<st.A[s].sdep<<endl;
		cur=max(cur, ((ll)count[s])*(2ll*((ll)st.A[s].sdep)-(1ll-par)));
	};*/
	
	work(0);
	
	f.clear();
	livres.clear();
	for(auto &u: vv) u=-1;
	for(int &u: count) u=0;
	work(1);
	
	cout<<cur<<'\n';
}

int main(){
	
	banana();
	
	int n_casos=1; //cin>>n_casos;
	
	while(n_casos--) caso_teste();
}

Compilation message (stderr)

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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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