Submission #348843

#	Time	Username	Problem	Language	Result	Execution time	Memory
348843		ahoraSoyPeor	Palindromes (APIO14_palindrome)	C++14	Compilation error	0 ms	0 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int N = 500'005;
const int MOD = 1'000'000'007;
const int LOGN = 17;

//int mul ( int A, int B ) { return int((ll(A)*ll(B))%ll(MOD)); }
//int add ( int A, int B ) { return A+B >= MOD? A+B-MOD: A+B; }
//int sub ( int A, int B ) { return add ( A, MOD-B ); }

struct palindromic_tree {
  struct node{
    int len, link;
    map <char,int> next;
  };
  vector <node> pt;
  int last, it;
  string s;
  palindromic_tree (string str = "") {
    pt.reserve ( s.size()+2 );
    s = '#', it = 1, last = 1; //# isn't used in string
    add_node (), add_node();
    pt[1].len = -1, pt[0].link = 1;
    for ( char &c: str ) add_letter ( c );
  }
  int add_node () {
    pt.push_back({});
    return pt.size()-1;
  }
  int get_link ( int v ) {
    while ( s[it-pt[v].len-2] != s[it-1] ) v = pt[v].link;
    return v;
  }
  void add_letter ( char c ) {
    s += c, ++it;
    last = get_link ( last );
    if ( !pt[last].next.count (c) ) {
      int curr = add_node ();
      pt[curr].len = pt[last].len+2;
      pt[curr].link = pt[get_link(pt[last].link)].next[c];
      pt[last].next[c] = curr;
    }
    last = pt[last].next[c];
  }
  node& operator[](int i) { return pt[i]; }
  int size() { return pt.size(); }
};


int main () {

  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef LOCAL
    freopen ( "in.txt", "r", stdin );
  #endif // LOCAL

  string str;
  cin >> str;

  palindromic_tree root (str);
  vector <pii> toSort (root.size()-2);
  for ( int i = 2; i < root.size(); ++i )
    toSort[i-2] = {root[i].len, i};
  sort ( toSort.rbegin(), toSort.rend() );
  ll maxi = 0;
  for ( pii it: toSort ) {
    root[root[it.ss].link].cnt += root[it.ss].cnt;
    maxi = max ( maxi, root[it.ss].cnt*it.ff );
  }
  cout << maxi << "\n";

  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:78:28: error: 'struct palindromic_tree::node' has no member named 'cnt'
   78 |     root[root[it.ss].link].cnt += root[it.ss].cnt;
      |                            ^~~
palindrome.cpp:78:47: error: 'struct palindromic_tree::node' has no member named 'cnt'
   78 |     root[root[it.ss].link].cnt += root[it.ss].cnt;
      |                                               ^~~
palindrome.cpp:79:36: error: 'struct palindromic_tree::node' has no member named 'cnt'
   79 |     maxi = max ( maxi, root[it.ss].cnt*it.ff );
      |                                    ^~~