oj.uz

Submission #439912

# Submission time Handle Problem Language Result Execution time Memory
439912 2021-07-01T07:56:54 Z codebuster_10 Palindromes (APIO14_palindrome) C++17
100 / 100
 68 ms 69740 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back

#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x;}
template<class H, class... T> void rd(H& h, T&... t) { rd(h); rd(t...);}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a);}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0;}

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}


void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  // remove this when size of input is not fixed.
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}


/*********************************************Look Below******************************************************************/








































/*
	* description :- palindromic tree for a string which is genralized version of kmp for palindromes.
	* indexing of palindromic tree starts from 1.
	* source :- http://adilet.org/blog/palindromic-tree/.
	* verification :- https://www.spoj.com/status/NUMOFPAL,deepkamal/
*/

template<int MAX_N,int ALPHABET>
struct palindromic_tree {
	
	static const int INF = 1e9;
	
	struct node {
		// the next node which stores c + palindrome + c
  	array<int,ALPHABET> next;
  	// length of the current palindrome
  	int length;
  	// maximum proper suffix of the current palindrome which is also a palindrome.
  	int suffix_link; 
  	// lazy value.
  	int lazy;
  	node(){
  		next.fill(-INF);
  		length = suffix_link = lazy = -INF;
  	}
	};

	// our string
	string s; 
	// our palindromic tree
	node tree[MAX_N];
	// total number of nodes
	int total_nodes;           
	// maximum suffix palindrome of present string.
	int max_suffix;	
	
	palindromic_tree() {
		// node 1 - root with length -1, node 2 - root with length 0
    tree[1].length = -1, tree[1].suffix_link = 1,	tree[1].lazy = 0;
    tree[2].length = 0, tree[2].suffix_link = 1,	tree[2].lazy = 0;
    total_nodes = 2; 
    max_suffix = 2;
	}
	
	bool add_char(char _c) {
		s.push_back(_c);
		int pos = int(s.size()) - 1;
		
  	int cur_suffix = max_suffix, cur_length = 0;
  	int c = s[pos] - 'a';

  	while(true){
      cur_length = tree[cur_suffix].length;
      if(pos - 1 - cur_length >= 0 && s[pos - 1 - cur_length] == s[pos]){
      	break;  
      } 
      cur_suffix = tree[cur_suffix].suffix_link;
  	}       
  	
  	if(tree[cur_suffix].next[c] > 0){  
      max_suffix = tree[cur_suffix].next[c];
      ++tree[max_suffix].lazy;
      return false;
  	}

  	int now = ++total_nodes;
  	
  	max_suffix = now;
  	tree[now].length = tree[cur_suffix].length + 2;
  	tree[cur_suffix].next[c] = now;
  	tree[now].lazy = 1;
  	
  	if(tree[now].length == 1){
    	tree[now].suffix_link = 2;
    	return true;
  	}

  	while(true){
    	cur_suffix = tree[cur_suffix].suffix_link;
    	cur_length = tree[cur_suffix].length;
    	if(pos - 1 - cur_length >= 0 && s[pos - 1 - cur_length] == s[pos]){
        tree[now].suffix_link = tree[cur_suffix].next[c];
        break;
    	}       
  	}          
  	return true;
	}
	
	void fun(){
		
		int best = 0;
		
		for(int i = total_nodes; i >= 1; --i){
			int j = tree[i].suffix_link;
			tree[j].lazy += tree[i].lazy;
			ckmax(best,tree[i].length * tree[i].lazy);
		}
		
		cout << best;
		
		return;
		
	}
};


palindromic_tree<300077,26> pdt;

signed main(){
  setIO();
	string s; rd(s);
	for(auto c : s) pdt.add_char(c);
	pdt.fun();
}

Compilation message

palindrome.cpp: In function 'void setIO(std::string)':
palindrome.cpp:82:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 68440 KB Output is correct
2 Correct 34 ms 68364 KB Output is correct
3 Correct 35 ms 68312 KB Output is correct
4 Correct 39 ms 68320 KB Output is correct
5 Correct 34 ms 68432 KB Output is correct
6 Correct 37 ms 68364 KB Output is correct
7 Correct 39 ms 68300 KB Output is correct
8 Correct 39 ms 68420 KB Output is correct
9 Correct 36 ms 68352 KB Output is correct
10 Correct 38 ms 68292 KB Output is correct
11 Correct 41 ms 68360 KB Output is correct
12 Correct 47 ms 68384 KB Output is correct
13 Correct 48 ms 68292 KB Output is correct
14 Correct 34 ms 68428 KB Output is correct
15 Correct 40 ms 68292 KB Output is correct
16 Correct 35 ms 68304 KB Output is correct
17 Correct 36 ms 68396 KB Output is correct
18 Correct 40 ms 68296 KB Output is correct
19 Correct 47 ms 68420 KB Output is correct
20 Correct 38 ms 68344 KB Output is correct
21 Correct 44 ms 68420 KB Output is correct
22 Correct 36 ms 68336 KB Output is correct
23 Correct 35 ms 68400 KB Output is correct
24 Correct 40 ms 68296 KB Output is correct
25 Correct 43 ms 68312 KB Output is correct
26 Correct 45 ms 68376 KB Output is correct
27 Correct 38 ms 68292 KB Output is correct
28 Correct 35 ms 68416 KB Output is correct
29 Correct 46 ms 68420 KB Output is correct
30 Correct 39 ms 68380 KB Output is correct
31 Correct 43 ms 68360 KB Output is correct
32 Correct 39 ms 68376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68420 KB Output is correct
2 Correct 44 ms 68340 KB Output is correct
3 Correct 44 ms 68344 KB Output is correct
4 Correct 36 ms 68428 KB Output is correct
5 Correct 37 ms 68324 KB Output is correct
6 Correct 42 ms 68420 KB Output is correct
7 Correct 39 ms 68440 KB Output is correct
8 Correct 36 ms 68380 KB Output is correct
9 Correct 45 ms 68292 KB Output is correct
10 Correct 39 ms 68420 KB Output is correct
11 Correct 38 ms 68332 KB Output is correct
12 Correct 38 ms 68420 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68460 KB Output is correct
2 Correct 37 ms 68420 KB Output is correct
3 Correct 44 ms 68396 KB Output is correct
4 Correct 38 ms 68440 KB Output is correct
5 Correct 37 ms 68364 KB Output is correct
6 Correct 39 ms 68428 KB Output is correct
7 Correct 36 ms 68380 KB Output is correct
8 Correct 39 ms 68432 KB Output is correct
9 Correct 43 ms 68372 KB Output is correct
10 Correct 44 ms 68380 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 68804 KB Output is correct
2 Correct 42 ms 68804 KB Output is correct
3 Correct 40 ms 68788 KB Output is correct
4 Correct 45 ms 68868 KB Output is correct
5 Correct 50 ms 68816 KB Output is correct
6 Correct 49 ms 68860 KB Output is correct
7 Correct 43 ms 68940 KB Output is correct
8 Correct 43 ms 68800 KB Output is correct
9 Correct 43 ms 68796 KB Output is correct
10 Correct 41 ms 68804 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 69708 KB Output is correct
2 Correct 59 ms 69656 KB Output is correct
3 Correct 59 ms 69700 KB Output is correct
4 Correct 53 ms 69708 KB Output is correct
5 Correct 60 ms 69740 KB Output is correct
6 Correct 55 ms 69660 KB Output is correct
7 Correct 68 ms 69708 KB Output is correct
8 Correct 43 ms 69716 KB Output is correct
9 Correct 43 ms 69740 KB Output is correct
10 Correct 62 ms 69632 KB Output is correct
11 Correct 51 ms 69708 KB Output is correct
12 Correct 52 ms 69708 KB Output is correct