Submission #39341

#	Time	Username	Problem	Language	Result	Execution time	Memory
39341		qoo2p5	Palindromes (APIO14_palindrome)	C++14	100 / 100	889 ms	17672 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
	if (x < 0) x += MOD;
}

ll mult(ll x, ll y) {
	return x * y % MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

vector<int> manaher(const string &s) {
	string t;
	for (char c : s) {
		t += '$';
		t += c;
	}
	t += '$';
	int n = sz(t);
	vector<int> res(n);
	int l = -1, r = -1;
	rep(i, 0, n) {
		int k = 1;
		if (i <= r) {
			k = min(r - i + 1, res[l + r - i]);
		}
		while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) {
			k++;
		}
		if (i + k - 1 > r) {
			l = i - k + 1;
			r = i + k - 1;
		}
		res[i] = k;
	}
	/*rep(i, 0, n) {
		int k = 1;
		while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) {
			k++;
		}
		res[i] = k;
	}*/
	return res;
}

vector<int> suff_arr(string s) {
	s += '$';
	int n = sz(s);
	vector<int> cl(n);
	rep(i, 0, n) {
		cl[i] = s[i];
	}
	vector<pair<pair<int, int>, int>> ids(n);
	vector<int> tmp(n);
	int A = max(n, 256);
	vector<int> cnt(A);
	for (int len = 1; len < n; len *= 2) {
		fill(all(cnt), 0);
		rep(i, 0, n) {
			int c = cl[(i + len) % n];
			cnt[c + 1]++;
		}
		rep(i, 1, A) {
			cnt[i] += cnt[i - 1];
		}
		rep(i, 0, n) {
			int c = cl[(i + len) % n];
			tmp[cnt[c]++] = i;
		}
		fill(all(cnt), 0);
		rep(i, 0, n) {
			int id = tmp[i];
			cnt[cl[id] + 1]++;
		}
		rep(i, 1, A) {
			cnt[i] += cnt[i - 1];
		}
		rep(i, 0, n) {
			int id = tmp[i];
			ids[cnt[cl[id]]++] = {{cl[id], cl[(id + len) % n]}, id};
		}
		
		int ptr = 0;
		rep(i, 0, n) {
			int j = i;
			cl[ids[i].second] = ptr;
			while (j + 1 < n && ids[j + 1].first == ids[j].first) cl[ids[++j].second] = ptr;
			ptr++;
			i = j;
		}
	}
	
	vector<int> res(n - 1);
	rep(i, 0, n - 1) {
		int pos = cl[i] - 1;
		assert(pos >= 0);
		res[pos] = i;
	}
	return res;
	
	/*int n = sz(s);
	vector<pair<string, int>> q(n);
	rep(i, 0, n) q[i] = {s.substr(i), i};
	sort(all(q));
	vector<int> res(n);
	rep(i, 0, n) res[i] = q[i].second;
	return res;*/
}

vector<int> get_lcp(const string &s, const vector<int> &arr) {
	int n = sz(s);
	assert(sz(s) == sz(arr));
	vector<int> res(n), pos(n);
	rep(i, 0, n) {
		pos[arr[i]] = i;
	}
	int k = 0;
	rep(i, 0, n) {
		if (k > 0) {
			k--;
		}
		
		int p = pos[i];
		if (p == n - 1) {
			k = 0;
		} else {
			int j = arr[p + 1];
			while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
				k++;
			}
		}
		
		res[p] = k;
	}
	return res;
	/*int n = sz(s);
	vector<int> res(n);
	rep(i, 0, n - 1) {
		int k = 0;
		int p = arr[i];
		int q = arr[i + 1];
		while (p + k < n && q + k < n && s[p + k] == s[q + k]) k++;
		res[i] = k;
	}
	return res;*/
}

const int N = (int) 3e5 + 123;

int p[N], cnt[N], rnk[N];

void init() {
	rep(i, 0, N) {
		p[i] = i;
		cnt[i] = 0;
		rnk[i] = 0;
	}
}

int get(int v) {
	return (p[v] == v ? v : (p[v] = get(p[v])));
}

void unite(int u, int v) {
	u = get(u);
	v = get(v);
	if (u == v) {
		return;
	}
	if (rnk[u] > rnk[v]) {
		swap(u, v);
	} else if (rnk[u] == rnk[v]) {
		rnk[v]++;
	}
	p[u] = v;
	cnt[v] += cnt[u];
}

void run() {
	string s;
	cin >> s;
	int n = sz(s);
	vector<int> pal = manaher(s);
	vector<int> arr = suff_arr(s);
	vector<int> lcp = get_lcp(s, arr);
	vector<int> pos(n);
	rep(i, 0, n) {
		pos[arr[i]] = i;
	}
	
	ll ans = 0;
	
	vector<pair<int, int>> by_lcp(n);
	rep(i, 0, n) {
		by_lcp[i] = {lcp[i], i};
	}
	sort(all(by_lcp));
	reverse(all(by_lcp));
	
	init();
	
	{
		vector<pair<int, int>> pals(n);
		rep(i, 0, n) {
			pals[i] = {pal[2 * i + 1] / 2, i};
		}
		sort(all(pals));
		reverse(all(pals));
		int ptr = 0;
		rep(i, 0, n) {
			int len = pals[i].first;
			while (ptr < n && by_lcp[ptr].first >= len) {
				unite(by_lcp[ptr].second, by_lcp[ptr].second + 1);
				ptr++;
			}
			int v = get(pos[pals[i].second]);
			cnt[v]++;
			maxi(ans, cnt[v] * (2LL * len - 1));
		}
	}
	
	init();
	
	{
		vector<pair<int, int>> pals(n - 1);
		rep(i, 1, n) {
			pals[i - 1] = {pal[2 * i] / 2, i};
		}
		sort(all(pals));
		reverse(all(pals));
		int ptr = 0;
		rep(i, 0, n - 1) {
			int len = pals[i].first;
			if (len == 0) {
				break;
			}
			while (ptr < n && by_lcp[ptr].first >= len) {
				unite(by_lcp[ptr].second, by_lcp[ptr].second + 1);
				ptr++;
			}
			int v = get(pos[pals[i].second]);
			cnt[v]++;
			maxi(ans, cnt[v] * 2LL * len);
		}
	}
	
	cout << ans << "\n";
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:72:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
                                        ^
palindrome.cpp:73:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
                                          ^

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