Submission #308041

#	Time	Username	Problem	Language	Result	Execution time	Memory
308041		Elephant52	Palindromes (APIO14_palindrome)	C++11	Compilation error	0 ms	0 KiB

palindrome

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;

#define INF 1000000000
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)

void setIO(string name) {
    freopen((name+".in").c_str(), "r", stdin); 
    freopen((name+".out").c_str(), "w", stdout);
}

string s;

typedef struct node {
    int next[26];
    ll len = 0, suflink = 0, num = 0;
    node() {};
} node;

node tree[300001];
int num, suf;
vi adj[300001];

bool add_letter(int pos) { //return 1 on new palindromes
    int cur = suf, letter = (s[pos]-'a'), curlen = 0;
    
    while(1) { //find longest palindromic suffix of s[0...pos-1] that can include s[pos]
        curlen = tree[cur].len;
        if (pos > curlen && s[pos-1-curlen] == s[pos]) break;
        cur = tree[cur].suflink;
    }
    
    if (tree[cur].next[letter]) { //if there exists a link from smaller palindrome to s[pos] + pal + s[pos] then do nothing
        suf = tree[cur].next[letter];
        tree[suf].num++;
        return 0;
    }
    
    //create a new palindrome with id num+1 in the tree
    
    suf = ++num;
    tree[num].num = 1;
    tree[num].len = tree[cur].len + 2; //add on s[pos]
    tree[cur].next[letter] = num;
    
    if (tree[num].len == 1) {
        tree[num].suflink = 2; //link to the empty palindrome
        adj[2].PB(num);
        return 1;
    } 
    
    while(1) {
        cur = tree[cur].suflink;
        curlen = tree[cur].len;
        if (pos > curlen && s[pos-1-curlen] == s[pos]) {
            tree[num].suflink = tree[cur].next[letter];
            adj[tree[cur].next[letter]].PB(num);
            break;
        }
    }
    
    return 1;
}



void dfs(int cur = 1, par = -1) {
    for (auto edge : adj[cur]) {
        if (edge != par) {
            dfs(edge, cur);
            tree[cur].num += tree[edge].num;
        }
    }
}

void init() {
    num = suf = 2;
    tree[1].len = -1, tree[2].len = 0;
    tree[1].suflink = tree[2].suflink = 1;
    adj[1].PB(2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> s;
    
    init();
    
    rep(i,0,s.length()) add_letter(i);
    
    ll ans = 0;
    
    dfs();
    
    rep(i,1,300001) ans = max(ans, tree[i].len * tree[i].num);
    
    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

palindrome.cpp:77:23: error: 'par' has not been declared
   77 | void dfs(int cur = 1, par = -1) {
      |                       ^~~
palindrome.cpp: In function 'void dfs(int, int)':
palindrome.cpp:79:21: error: 'par' was not declared in this scope
   79 |         if (edge != par) {
      |                     ^~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:15:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,a,b) for (int i = a; i < b; i++)
......
  100 |     rep(i,0,s.length()) add_letter(i);
      |         ~~~~~~~~~~~~~~                
palindrome.cpp:100:5: note: in expansion of macro 'rep'
  100 |     rep(i,0,s.length()) add_letter(i);
      |     ^~~
palindrome.cpp: In function 'void setIO(std::string)':
palindrome.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~