oj.uz

Submission #947643

# Submission time Handle Problem Language Result Execution time Memory
947643 2024-03-16T17:29:38 Z vjudge1 Palindromes (APIO14_palindrome) C++17
100 / 100
 13 ms 39140 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::size; 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 36188 KB Output is correct
2 Correct 7 ms 36184 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 36188 KB Output is correct
6 Correct 5 ms 36096 KB Output is correct
7 Correct 5 ms 36188 KB Output is correct
8 Correct 5 ms 36184 KB Output is correct
9 Correct 5 ms 36184 KB Output is correct
10 Correct 6 ms 36188 KB Output is correct
11 Correct 5 ms 36188 KB Output is correct
12 Correct 5 ms 36184 KB Output is correct
13 Correct 5 ms 36188 KB Output is correct
14 Correct 5 ms 36056 KB Output is correct
15 Correct 5 ms 36188 KB Output is correct
16 Correct 5 ms 36188 KB Output is correct
17 Correct 5 ms 36188 KB Output is correct
18 Correct 5 ms 36188 KB Output is correct
19 Correct 6 ms 36184 KB Output is correct
20 Correct 6 ms 36188 KB Output is correct
21 Correct 5 ms 36188 KB Output is correct
22 Correct 5 ms 36060 KB Output is correct
23 Correct 5 ms 36188 KB Output is correct
24 Correct 5 ms 36188 KB Output is correct
25 Correct 5 ms 36060 KB Output is correct
26 Correct 5 ms 36188 KB Output is correct
27 Correct 5 ms 36188 KB Output is correct
28 Correct 5 ms 36188 KB Output is correct
29 Correct 5 ms 36104 KB Output is correct
30 Correct 6 ms 36188 KB Output is correct
31 Correct 5 ms 36184 KB Output is correct
32 Correct 5 ms 36188 KB Output is correct

Subtask #2
15.0 / 15.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 5 ms 36388 KB Output is correct
4 Correct 5 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 5 ms 36084 KB Output is correct
9 Correct 5 ms 36188 KB Output is correct
10 Correct 5 ms 36012 KB Output is correct
11 Correct 5 ms 36052 KB Output is correct
12 Correct 7 ms 36060 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36188 KB Output is correct
2 Correct 6 ms 36184 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 36120 KB Output is correct
6 Correct 5 ms 36188 KB Output is correct
7 Correct 5 ms 36100 KB Output is correct
8 Correct 5 ms 36092 KB Output is correct
9 Correct 5 ms 36188 KB Output is correct
10 Correct 5 ms 36140 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38488 KB Output is correct
2 Correct 7 ms 38492 KB Output is correct
3 Correct 8 ms 38492 KB Output is correct
4 Correct 7 ms 38492 KB Output is correct
5 Correct 7 ms 38488 KB Output is correct
6 Correct 6 ms 38488 KB Output is correct
7 Correct 7 ms 38492 KB Output is correct
8 Correct 6 ms 36188 KB Output is correct
9 Correct 6 ms 36444 KB Output is correct
10 Correct 7 ms 38748 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38628 KB Output is correct
2 Correct 13 ms 38628 KB Output is correct
3 Correct 13 ms 38628 KB Output is correct
4 Correct 12 ms 38880 KB Output is correct
5 Correct 11 ms 38836 KB Output is correct
6 Correct 11 ms 38628 KB Output is correct
7 Correct 11 ms 38628 KB Output is correct
8 Correct 9 ms 36808 KB Output is correct
9 Correct 9 ms 36836 KB Output is correct
10 Correct 10 ms 39140 KB Output is correct
11 Correct 11 ms 39140 KB Output is correct
12 Correct 10 ms 36940 KB Output is correct