oj.uz

Submission #924829

# Submission time Handle Problem Language Result Execution time Memory
924829 2024-02-09T20:05:24 Z arneves Palindromes (APIO14_palindrome) C++17
73 / 100
 1000 ms 129868 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);
	
	unordered_map<int, set<int>> vv(MX);
	vector<int> count(MX, 0);
	
	ll cur=0;
	
	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].find(u)!=vv[s].end()) vv[s].erase(u), count[s]++;
					else vv[s].insert(u);
				}
				
				vv.erase(yi);
				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)));
	};
	
	dfs(dfs, 0, 0);
	
	vv.clear();
	//for(auto &u: vv) u.clear();
	for(int &u: count) u=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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 4 ms 14684 KB Output is correct
5 Correct 5 ms 14684 KB Output is correct
6 Correct 4 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 4 ms 14684 KB Output is correct
11 Correct 5 ms 14848 KB Output is correct
12 Correct 4 ms 14684 KB Output is correct
13 Correct 4 ms 14684 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 4 ms 14684 KB Output is correct
16 Correct 4 ms 14680 KB Output is correct
17 Correct 4 ms 14684 KB Output is correct
18 Correct 5 ms 14680 KB Output is correct
19 Correct 5 ms 14680 KB Output is correct
20 Correct 4 ms 14684 KB Output is correct
21 Correct 4 ms 14684 KB Output is correct
22 Correct 4 ms 14684 KB Output is correct
23 Correct 4 ms 14684 KB Output is correct
24 Correct 5 ms 14772 KB Output is correct
25 Correct 4 ms 14684 KB Output is correct
26 Correct 5 ms 14684 KB Output is correct
27 Correct 5 ms 14684 KB Output is correct
28 Correct 5 ms 14684 KB Output is correct
29 Correct 5 ms 14684 KB Output is correct
30 Correct 4 ms 14684 KB Output is correct
31 Correct 4 ms 14684 KB Output is correct
32 Correct 6 ms 14684 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15124 KB Output is correct
3 Correct 5 ms 15196 KB Output is correct
4 Correct 6 ms 14940 KB Output is correct
5 Correct 7 ms 15196 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 8 ms 14940 KB Output is correct
8 Correct 7 ms 17244 KB Output is correct
9 Correct 6 ms 14812 KB Output is correct
10 Correct 8 ms 16988 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 7 ms 14940 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20060 KB Output is correct
2 Correct 19 ms 17500 KB Output is correct
3 Correct 20 ms 20568 KB Output is correct
4 Correct 18 ms 19544 KB Output is correct
5 Correct 43 ms 17340 KB Output is correct
6 Correct 37 ms 17232 KB Output is correct
7 Correct 20 ms 18012 KB Output is correct
8 Correct 29 ms 15964 KB Output is correct
9 Correct 29 ms 17496 KB Output is correct
10 Correct 46 ms 16984 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 59016 KB Output is correct
2 Correct 204 ms 45716 KB Output is correct
3 Correct 166 ms 54520 KB Output is correct
4 Correct 152 ms 44684 KB Output is correct
5 Correct 637 ms 40904 KB Output is correct
6 Correct 463 ms 41100 KB Output is correct
7 Correct 249 ms 33928 KB Output is correct
8 Correct 371 ms 29832 KB Output is correct
9 Correct 294 ms 32648 KB Output is correct
10 Correct 611 ms 39340 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 107908 KB Output is correct
2 Correct 624 ms 74852 KB Output is correct
3 Correct 525 ms 129868 KB Output is correct
4 Correct 458 ms 81500 KB Output is correct
5 Execution timed out 1056 ms 72284 KB Time limit exceeded
6 Halted 0 ms 0 KB -