oj.uz

Submission #924861

# Submission time Handle Problem Language Result Execution time Memory
924861 2024-02-10T00:11:23 Z arneves Palindromes (APIO14_palindrome) C++17
73 / 100
 757 ms 131072 KB 
/*
           ______  _____  _______ _     _ _______ __   _  _____  _  _  _
          |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
          |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
        
        
                   .      .           .      .           .      .    
                   _\/  \/_           _\/  \/_           _\/  \/_    
                    _\/\/_             _\/\/_             _\/\/_     
                _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 
                 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  
                    _/\/\_             _/\/\_             _/\/\_     
                    /\  /\             /\  /\             /\  /\     
                   '      '           '      '           '      '    
        
*/

#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);
	
	set<int> vv[MX];
	vector<int> count(MX, 0);
	
	ll cur=0;
	
	auto work=[&](int par) -> void {
		
		int mem[MX];
		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--;
		while(p>=0){
			int s=mem[p];
			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);
					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;
				}
			}
			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);
	
	for(int i=0; i<MX; i++) vv[i].clear();
	//for(auto &u: vv) u.clear();
	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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66024 KB Output is correct
2 Correct 48 ms 66200 KB Output is correct
3 Correct 57 ms 66128 KB Output is correct
4 Correct 57 ms 66132 KB Output is correct
5 Correct 48 ms 66116 KB Output is correct
6 Correct 47 ms 66132 KB Output is correct
7 Correct 47 ms 66136 KB Output is correct
8 Correct 47 ms 66140 KB Output is correct
9 Correct 47 ms 66128 KB Output is correct
10 Correct 51 ms 66384 KB Output is correct
11 Correct 47 ms 66128 KB Output is correct
12 Correct 47 ms 66384 KB Output is correct
13 Correct 47 ms 66036 KB Output is correct
14 Correct 47 ms 66132 KB Output is correct
15 Correct 47 ms 66128 KB Output is correct
16 Correct 52 ms 66388 KB Output is correct
17 Correct 48 ms 66212 KB Output is correct
18 Correct 48 ms 66140 KB Output is correct
19 Correct 47 ms 66128 KB Output is correct
20 Correct 48 ms 66128 KB Output is correct
21 Correct 56 ms 66192 KB Output is correct
22 Correct 53 ms 66128 KB Output is correct
23 Correct 47 ms 66128 KB Output is correct
24 Correct 48 ms 66208 KB Output is correct
25 Correct 50 ms 66128 KB Output is correct
26 Correct 47 ms 66012 KB Output is correct
27 Correct 47 ms 66128 KB Output is correct
28 Correct 47 ms 66204 KB Output is correct
29 Correct 49 ms 66228 KB Output is correct
30 Correct 47 ms 66132 KB Output is correct
31 Correct 47 ms 66200 KB Output is correct
32 Correct 51 ms 66132 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 66452 KB Output is correct
2 Correct 49 ms 66384 KB Output is correct
3 Correct 48 ms 66128 KB Output is correct
4 Correct 49 ms 66388 KB Output is correct
5 Correct 48 ms 66184 KB Output is correct
6 Correct 50 ms 66400 KB Output is correct
7 Correct 50 ms 66388 KB Output is correct
8 Correct 49 ms 66304 KB Output is correct
9 Correct 49 ms 66276 KB Output is correct
10 Correct 49 ms 68272 KB Output is correct
11 Correct 50 ms 66408 KB Output is correct
12 Correct 49 ms 66396 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 68688 KB Output is correct
2 Correct 59 ms 68352 KB Output is correct
3 Correct 56 ms 67664 KB Output is correct
4 Correct 60 ms 68068 KB Output is correct
5 Correct 96 ms 68432 KB Output is correct
6 Correct 75 ms 69924 KB Output is correct
7 Correct 59 ms 68436 KB Output is correct
8 Correct 71 ms 68244 KB Output is correct
9 Correct 73 ms 68436 KB Output is correct
10 Correct 81 ms 68692 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 93420 KB Output is correct
2 Correct 178 ms 91428 KB Output is correct
3 Correct 155 ms 84920 KB Output is correct
4 Correct 149 ms 83340 KB Output is correct
5 Correct 727 ms 92588 KB Output is correct
6 Correct 464 ms 92644 KB Output is correct
7 Correct 254 ms 85616 KB Output is correct
8 Correct 489 ms 87372 KB Output is correct
9 Correct 375 ms 84748 KB Output is correct
10 Correct 757 ms 92396 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 381 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -