oj.uz

Submission #947638

# Submission time Handle Problem Language Result Execution time Memory
947638 2024-03-16T17:21:43 Z vjudge1 Palindromes (APIO14_palindrome) C++17
0 / 100
 14 ms 38368 KB 
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}



const int N = 1e6+3, K = 26;
//====================================================================//


const int MAXN = 3e5+7; ///max length of string+3
namespace PalTree {
  struct node {
    int len; ///length of the pal of this node
    int sufflink; ///largest suff pal of this node
    int chain;///#of nodes on chain of suff links
    int next[26];///next[c] is the pal by adding c
  } tr[MAXN];
  int size;///# of nodes currently in Pal tr
  int suff;///max suff pal of curr prcessed prefix
  string s;///string we will built our Paltr on
  bool addLetter(int pos) {
    int cur = suff, curlen = 0, let = s[pos]-'a';
    while (true) {
      curlen = tr[cur].len;
      if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
        break; cur = tr[cur].sufflink;
    }
    if (tr[cur].next[let]) {
      suff = tr[cur].next[let]; return false;
    }
    suff = ++size; tr[cur].next[let] = size;
    tr[size].len = tr[cur].len+2;
    if (tr[size].len == 1) {
      tr[size].sufflink=2; tr[size].chain=1;
      return true;
    }
    while (true) {
      cur=tr[cur].sufflink;curlen=tr[cur].len;
     if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]){
        tr[size].sufflink = tr[cur].next[let];
        break;
      }
    }
    tr[size].chain=1+tr[tr[size].sufflink].chain;
    return true;
  }
  void initTree() {
    memset(tr,0,sizeof tr);///CAREFUL:TESTCASES
    size = 2; suff = 2;
    tr[1].len = -1; tr[1].sufflink = 1;
    tr[2].len = 0; tr[2].sufflink = 1;
  }
}

int cnt[N];
void testcase(){
	cin >> PalTree::s;
	PalTree::initTree();
	for(int i = 0; i < PalTree::s.size(); i++){
		PalTree::addLetter(i);
		cnt[PalTree::suff]++;
	}
	ll ans = 0;
	for(int i = PalTree::suff; i >= 2; i--){
		ans = max(ans, (ll)cnt[i] * PalTree::tr[i].len);
		cnt[PalTree::tr[i].sufflink] += cnt[i];
	}
	cout << ans << "\n";
	
}




int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int T = 1;
	//cin >> T;
	
	for(int qq = 1; qq <= T; ++qq){
		//cout << "Case #" << qq << ": ";
		testcase();
	}
	return 0;
}

Compilation message

palindrome.cpp: In function 'bool PalTree::addLetter(int)':
palindrome.cpp:100:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  100 |       if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
      |       ^~
palindrome.cpp:101:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  101 |         break; cur = tr[cur].sufflink;
      |                ^~~
palindrome.cpp: In function 'void testcase()':
palindrome.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for(int i = 0; i < PalTree::s.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36184 KB Output is correct
2 Correct 5 ms 36188 KB Output is correct
3 Correct 5 ms 36188 KB Output is correct
4 Correct 6 ms 36188 KB Output is correct
5 Correct 5 ms 36188 KB Output is correct
6 Correct 6 ms 36188 KB Output is correct
7 Correct 5 ms 36188 KB Output is correct
8 Correct 6 ms 36188 KB Output is correct
9 Correct 5 ms 36200 KB Output is correct
10 Correct 6 ms 36188 KB Output is correct
11 Correct 6 ms 36096 KB Output is correct
12 Incorrect 5 ms 36188 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36184 KB Output is correct
2 Correct 5 ms 36188 KB Output is correct
3 Correct 5 ms 36188 KB Output is correct
4 Correct 5 ms 36188 KB Output is correct
5 Correct 5 ms 36184 KB Output is correct
6 Correct 6 ms 36060 KB Output is correct
7 Correct 5 ms 36188 KB Output is correct
8 Correct 5 ms 36188 KB Output is correct
9 Correct 5 ms 36188 KB Output is correct
10 Incorrect 5 ms 36184 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36188 KB Output is correct
2 Correct 5 ms 36188 KB Output is correct
3 Correct 6 ms 36188 KB Output is correct
4 Correct 5 ms 36140 KB Output is correct
5 Correct 5 ms 36188 KB Output is correct
6 Correct 5 ms 36104 KB Output is correct
7 Correct 5 ms 36188 KB Output is correct
8 Incorrect 5 ms 36188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 36700 KB Output is correct
2 Correct 7 ms 36836 KB Output is correct
3 Correct 8 ms 36700 KB Output is correct
4 Correct 7 ms 36700 KB Output is correct
5 Correct 7 ms 36696 KB Output is correct
6 Correct 7 ms 36700 KB Output is correct
7 Correct 7 ms 36816 KB Output is correct
8 Incorrect 8 ms 36328 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37856 KB Output is correct
2 Correct 12 ms 37860 KB Output is correct
3 Correct 14 ms 38368 KB Output is correct
4 Correct 13 ms 37860 KB Output is correct
5 Correct 12 ms 37856 KB Output is correct
6 Correct 13 ms 37860 KB Output is correct
7 Incorrect 10 ms 37860 KB Output isn't correct
8 Halted 0 ms 0 KB -