oj.uz

Submission #554538

# Submission time Handle Problem Language Result Execution time Memory
554538 2022-04-28T16:17:37 Z kwongweng Palindromes (APIO14_palindrome) C++17
100 / 100
 63 ms 71180 KB 
/*
Solution for APIO 2014 - Palindrome
Tags : palindromic tree
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

string s;
const int N = 300031;

struct Node{
    int len; 
    int nxt[26]; 
    vi edges; 
    int sufflink; 
    int cnt; 

    //len = length of palindrome
    //nxt[i] = palindrome formed by adding ith alphabet to current palindrome
    //edges = list of palindromes that contains this palindrome as longest proper suffix that is a palindrome
    //sufflink = longest palindrome that is proper suffix of current palindrome
    //cnt = # occurence of this palindrome
} tree[N];

int num, suff;

//initialise the tree
void init(){
    num = 2; suff = 2;
    tree[1].len = -1; tree[1].sufflink = 1;
    tree[2].len = 0; tree[2].sufflink = 1;
    tree[1].edges.pb(2);
}

void add(int pos){
    int cur = suff, curlen = 0;
    int letter = s[pos]-'a';

    while (true){
        curlen = tree[cur].len;
        if (pos-curlen-1 >= 0 && s[pos-curlen-1] == s[pos]){
            break;
        }
        cur = tree[cur].sufflink;
    }

    if (tree[cur].nxt[letter]){
        suff = tree[cur].nxt[letter];
        tree[suff].cnt++;
        return;
    }

    num++;
    suff = num;
    tree[num].len = tree[cur].len + 2;
    tree[num].cnt = 1;
    tree[cur].nxt[letter] = num;

    if (tree[num].len == 1){
        tree[num].sufflink = 2;
        tree[2].edges.pb(num);
        return;
    }

    while (true){
        cur = tree[cur].sufflink;
        curlen = tree[cur].len;
        if (pos-curlen-1 >= 0 && s[pos-curlen-1] == s[pos]){
            int val = tree[cur].nxt[letter];
            tree[num].sufflink = val;
            tree[val].edges.pb(num);
            break;
        }
    }    
}

ll ans = 0;
void dfs(int u){
    for (int v : tree[u].edges){
        dfs(v);
        tree[u].cnt += tree[v].cnt;
    }
    ans = max(ans, (ll) tree[u].cnt * (ll) tree[u].len);
}

void solve(){
    cin >> s;
    int n = s.size();
    init();
    FOR(i,0,n){
        add(i);
    }
    dfs(1);
    cout << ans;
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

palindrome.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
palindrome.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42580 KB Output is correct
2 Correct 19 ms 42556 KB Output is correct
3 Correct 19 ms 42568 KB Output is correct
4 Correct 19 ms 42512 KB Output is correct
5 Correct 18 ms 42516 KB Output is correct
6 Correct 19 ms 42500 KB Output is correct
7 Correct 20 ms 42580 KB Output is correct
8 Correct 18 ms 42580 KB Output is correct
9 Correct 24 ms 42584 KB Output is correct
10 Correct 21 ms 42580 KB Output is correct
11 Correct 21 ms 42484 KB Output is correct
12 Correct 22 ms 42536 KB Output is correct
13 Correct 19 ms 42580 KB Output is correct
14 Correct 20 ms 42576 KB Output is correct
15 Correct 22 ms 42508 KB Output is correct
16 Correct 20 ms 42500 KB Output is correct
17 Correct 20 ms 42500 KB Output is correct
18 Correct 20 ms 42544 KB Output is correct
19 Correct 20 ms 42580 KB Output is correct
20 Correct 19 ms 42488 KB Output is correct
21 Correct 21 ms 42596 KB Output is correct
22 Correct 21 ms 42596 KB Output is correct
23 Correct 22 ms 42580 KB Output is correct
24 Correct 20 ms 42568 KB Output is correct
25 Correct 18 ms 42548 KB Output is correct
26 Correct 19 ms 42580 KB Output is correct
27 Correct 19 ms 42592 KB Output is correct
28 Correct 19 ms 42580 KB Output is correct
29 Correct 20 ms 42580 KB Output is correct
30 Correct 20 ms 42560 KB Output is correct
31 Correct 25 ms 42544 KB Output is correct
32 Correct 20 ms 42580 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42576 KB Output is correct
2 Correct 20 ms 42544 KB Output is correct
3 Correct 20 ms 42596 KB Output is correct
4 Correct 20 ms 42604 KB Output is correct
5 Correct 24 ms 42600 KB Output is correct
6 Correct 20 ms 42664 KB Output is correct
7 Correct 19 ms 42580 KB Output is correct
8 Correct 20 ms 42556 KB Output is correct
9 Correct 20 ms 42580 KB Output is correct
10 Correct 22 ms 42580 KB Output is correct
11 Correct 21 ms 42580 KB Output is correct
12 Correct 24 ms 42580 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43136 KB Output is correct
2 Correct 20 ms 43092 KB Output is correct
3 Correct 21 ms 43476 KB Output is correct
4 Correct 21 ms 43388 KB Output is correct
5 Correct 21 ms 42676 KB Output is correct
6 Correct 20 ms 42848 KB Output is correct
7 Correct 25 ms 42972 KB Output is correct
8 Correct 21 ms 42504 KB Output is correct
9 Correct 23 ms 42528 KB Output is correct
10 Correct 19 ms 42580 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48952 KB Output is correct
2 Correct 29 ms 47568 KB Output is correct
3 Correct 33 ms 52172 KB Output is correct
4 Correct 30 ms 49828 KB Output is correct
5 Correct 30 ms 43860 KB Output is correct
6 Correct 26 ms 44884 KB Output is correct
7 Correct 31 ms 46064 KB Output is correct
8 Correct 24 ms 42844 KB Output is correct
9 Correct 31 ms 44776 KB Output is correct
10 Correct 36 ms 43728 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 61760 KB Output is correct
2 Correct 49 ms 54984 KB Output is correct
3 Correct 56 ms 71180 KB Output is correct
4 Correct 48 ms 59088 KB Output is correct
5 Correct 63 ms 47340 KB Output is correct
6 Correct 49 ms 54208 KB Output is correct
7 Correct 44 ms 52060 KB Output is correct
8 Correct 25 ms 43348 KB Output is correct
9 Correct 25 ms 43440 KB Output is correct
10 Correct 52 ms 46656 KB Output is correct
11 Correct 51 ms 55636 KB Output is correct
12 Correct 27 ms 45736 KB Output is correct