Submission #954417

#	Time	Username	Problem	Language	Result	Execution time	Memory
954417		hocln	Palindromes (APIO14_palindrome)	C++17	100 / 100	43 ms	118756 KiB

palindrome

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
const int N = 1e6+15;
ll ans[N];
struct node {
    int next[26];
    int len;
    int sufflink;
    int num;
    int sum = 0;
};

int len;
node T[N]; 
string s;
int num;            // node 1 - root with len -1, node 2 - root with len 0
int suff;           // max suffix palindrome

bool addLetter(int pos) {
    int cur = suff, curlen = 0;
    int let = s[pos] - 'a';

    while (true) {
        curlen = T[cur].len;
        if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])     
            break;  
        cur = T[cur].sufflink;
    }       
    if (T[cur].next[let]) {  
		++T[suff = T[cur].next[let]].sum;
        return false;
    }

    num++;
    suff = num;
    ++T[num].sum;
    T[num].len = T[cur].len + 2;
    T[cur].next[let] = num;

    if (T[num].len == 1) {
        T[num].sufflink = 2;
        T[num].num = 1;
        return true;
    }

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

    T[num].num = 1 + T[T[num].sufflink].num;

    return true;
}

void initTree() {
    num = 2; suff = 2;
    T[1].len = -1; T[1].sufflink = 1;
    T[2].len = 0; T[2].sufflink = 1;
}

// sn dsu and sn sgmt
inline void solve_test() {
	cin >> s;
	int n = s.size();
	initTree();
	for(int i = 0;i < n;i++) {
		addLetter(i);
	}
	ll rans = 0;
	for(int i = num;i > 2;--i) {
		T[T[i].sufflink].sum += T[i].sum;
		chmax(rans, T[i].sum *1LL* T[i].len);
	}
	cout << rans;
}
int main()
{
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    //freopen("convention2.in", "r", stdin);
    //freopen("convention2.out", "w", stdout);
	//cout << "Case #" << tc << ": " << ans << '\n';
	//cout << fixed << setprecision(15);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
		++tc;
        solve_test();
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27