oj.uz

Submission #924863

# Submission time Handle Problem Language Result Execution time Memory
924863 2024-02-10T00:35:42 Z arneves Palindromes (APIO14_palindrome) C++17
73 / 100
 612 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);
	
	vector<set<int>> vv(MX);
	vector<int> count(MX, 0);
	
	ll cur=0;
	
	auto work=[&](int par) -> void {
		
		vector<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 26 ms 66136 KB Output is correct
2 Correct 20 ms 66140 KB Output is correct
3 Correct 19 ms 66140 KB Output is correct
4 Correct 21 ms 66136 KB Output is correct
5 Correct 20 ms 66136 KB Output is correct
6 Correct 21 ms 66140 KB Output is correct
7 Correct 22 ms 66228 KB Output is correct
8 Correct 20 ms 66140 KB Output is correct
9 Correct 20 ms 66140 KB Output is correct
10 Correct 20 ms 66140 KB Output is correct
11 Correct 21 ms 66140 KB Output is correct
12 Correct 20 ms 66136 KB Output is correct
13 Correct 20 ms 66156 KB Output is correct
14 Correct 21 ms 66140 KB Output is correct
15 Correct 19 ms 66140 KB Output is correct
16 Correct 21 ms 66184 KB Output is correct
17 Correct 20 ms 66140 KB Output is correct
18 Correct 20 ms 66140 KB Output is correct
19 Correct 19 ms 66140 KB Output is correct
20 Correct 20 ms 66140 KB Output is correct
21 Correct 20 ms 66112 KB Output is correct
22 Correct 20 ms 66216 KB Output is correct
23 Correct 20 ms 66140 KB Output is correct
24 Correct 20 ms 66140 KB Output is correct
25 Correct 19 ms 66140 KB Output is correct
26 Correct 20 ms 66200 KB Output is correct
27 Correct 20 ms 66140 KB Output is correct
28 Correct 24 ms 66188 KB Output is correct
29 Correct 20 ms 66140 KB Output is correct
30 Correct 20 ms 66140 KB Output is correct
31 Correct 20 ms 66136 KB Output is correct
32 Correct 20 ms 66140 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 66396 KB Output is correct
2 Correct 21 ms 66648 KB Output is correct
3 Correct 21 ms 66392 KB Output is correct
4 Correct 20 ms 66396 KB Output is correct
5 Correct 21 ms 66396 KB Output is correct
6 Correct 21 ms 66396 KB Output is correct
7 Correct 23 ms 68444 KB Output is correct
8 Correct 20 ms 66396 KB Output is correct
9 Correct 22 ms 66328 KB Output is correct
10 Correct 23 ms 66380 KB Output is correct
11 Correct 22 ms 68444 KB Output is correct
12 Correct 23 ms 66392 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 68732 KB Output is correct
2 Correct 31 ms 68276 KB Output is correct
3 Correct 29 ms 67840 KB Output is correct
4 Correct 29 ms 68956 KB Output is correct
5 Correct 53 ms 68608 KB Output is correct
6 Correct 48 ms 68444 KB Output is correct
7 Correct 34 ms 70152 KB Output is correct
8 Correct 45 ms 68084 KB Output is correct
9 Correct 45 ms 70236 KB Output is correct
10 Correct 54 ms 68692 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 93496 KB Output is correct
2 Correct 152 ms 90564 KB Output is correct
3 Correct 136 ms 83080 KB Output is correct
4 Correct 133 ms 82156 KB Output is correct
5 Correct 568 ms 93240 KB Output is correct
6 Correct 423 ms 92652 KB Output is correct
7 Correct 218 ms 85556 KB Output is correct
8 Correct 442 ms 86088 KB Output is correct
9 Correct 338 ms 86208 KB Output is correct
10 Correct 612 ms 91572 KB Output is correct

Subtask #5
0 / 27.0

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