oj.uz

Submission #312151

# Submission time Handle Problem Language Result Execution time Memory
312151 2020-10-12T13:56:32 Z hohohaha Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 36752 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define ii pair<int, int>
#define iii pair<ii, int>

#define mp make_pair
#define eb emplace_back

#define vi vector<int>
#define vii vector<ii>
#define viii vector<iii>

#define fi first
#define se second
#define xx fi.fi
#define yy fi.se
#define zz se
int n, mhash[600005], rnk[600005], sa[600005], lcp[600005], even[600006], odd[600005], par[600005], w[3000005], ans, mxw;
stack<int> st;
string s;
int f(int a, int b, int c)
{
	assert(a<=1e6 and b<=1e6);
	return a*(int)1e9+b*(int)50+c;
}
void build(int len, int N)
{
	if(len==1) 
	{
		for(int i=1; i<=N; i++)
		{
			mhash[i] = s[i] - 0;
		}
	}
	else
	{
		map<int, int> M;
		int hlf = len>>1;
		build(hlf, N);
		for(int i=1; i<=N; i++)
		{
			mhash[i] = f(mhash[i], mhash[i+hlf], (len&1? s[i+len-1] - 0: 0));
			M[mhash[i]] = 0;
		}
		int curp = 0;
		for(auto& x: M)
		{
			x.se = ++curp;
		}
		for(int i=1; i<=N; i++)
		{
			mhash[i] = M[mhash[i]];
		}
	}
}
bool cmp(int a, int b)
{
	return mhash[a]<mhash[b];
}
int root(int x)
{
	return par[x]<0? x: par[x] = root(par[x]);
}
void join(int x, int y)
{
	x = root(x), y = root(y);
	if(x==y) return;
	if(par[x]>par[y]) swap(x, y);
	par[x]+=par[y];
	w[x]+=w[y];
	par[y] = x;
	w[y] = 0;
	mxw = max(mxw, w[x]);
}
void add(int x)
{
	x = root(x);
	w[x]++;
	mxw = max(mxw, w[x]);
}
void dsu(int arr[], bool bodd)
{
	for(int i=1; i<=n; i++)
	{
		par[i] = -1;
		w[i] = 0;
	}
	mxw = 0;
	priority_queue<ii> edge, el;
	for(int i=1; i<=n-1; i++) edge.push({lcp[i], i});
	for(int i=1; i<=n; i++) el.push({arr[sa[i]], i});
	for(int len = n; len>=1; len--)
	{
		while(!el.empty() and el.top().fi>=len)
		{
			add(el.top().se);
			el.pop();
		}
		while(!edge.empty() and edge.top().fi>=len) 
		{
			join(edge.top().se, edge.top().se+1); // dit me nham thanh .fi moi cay chu
			edge.pop();
		}
		ans = max(ans, mxw*(2*len-bodd));
	}
}
signed main()
{
// 	freopen(".inp", "r", stdin);
// 	freopen(".out", "w", stdout);
 	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s; n = s.length();
    s = '$'+s+char('a'-1)+s;
    build(n, n); // ban dau la build(n, n)
    for(int i=1; i<=n; i++)
    {
    	sa[i] = i;
	}
	sort(sa+1, sa+n+1, cmp);
	for(int i=1; i<=n; i++)
	{
		rnk[sa[i]] = i;
	}
	int curl = 0;
	for(int i=1; i<=n; i++)
	{
		if(rnk[i]==n) 
		{
			lcp[rnk[i]] = 0;
			continue;
		}
		int j = sa[rnk[i]+1];
		while(s[i+curl]==s[j+curl])
		{
			curl++;
		}
		lcp[rnk[i]] = curl;
		if(curl) curl--;
	}
	int l = 0, r = 0;
	for(int i=1; i<=n; i++)
	{
		if(l<=i and i<=r)
		{
			odd[i] = min(odd[l+r-i], r-i+1);
		}
		while(i-odd[i]>=1 and i+odd[i]<=n and s[i-odd[i]]==s[i+odd[i]]) 
		{
			odd[i]++;
		}
		if(odd[i] and r<i+odd[i]-1)
		{
			r = i+odd[i]-1;
			l = i-odd[i]+1;
		}
	}
	l = 0, r = 0;
	for(int i=2; i<=n; i++)
	{
		if(l<=i-1 and i<=r)
		{
			even[i] = min(even[l+r-i+1], r-i+1); // luc dau quen min o cho nay, toang vai. Nho lan sau phai co!. 
		}
		while(i-1-even[i]>=1 and i+even[i]<=n and s[i-1-even[i]] == s[i+even[i]])  even[i]++;
		if(even[i] and r<i+even[i]-1) 
		{
			r = i+even[i]-1;
			l = i-even[i];
		}
	}
	dsu(odd, 1);
	dsu(even, 0);
	cout<<ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 396 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1580 KB Output is correct
2 Correct 15 ms 1580 KB Output is correct
3 Correct 12 ms 1676 KB Output is correct
4 Correct 16 ms 1676 KB Output is correct
5 Correct 25 ms 1580 KB Output is correct
6 Correct 24 ms 1664 KB Output is correct
7 Correct 19 ms 1664 KB Output is correct
8 Correct 57 ms 1676 KB Output is correct
9 Correct 58 ms 1668 KB Output is correct
10 Correct 23 ms 1676 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 12312 KB Output is correct
2 Correct 215 ms 12440 KB Output is correct
3 Correct 139 ms 13208 KB Output is correct
4 Correct 187 ms 13208 KB Output is correct
5 Correct 491 ms 12440 KB Output is correct
6 Correct 494 ms 12568 KB Output is correct
7 Correct 421 ms 12952 KB Output is correct
8 Execution timed out 1089 ms 7704 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 36400 KB Output is correct
2 Execution timed out 1012 ms 36752 KB Time limit exceeded
3 Halted 0 ms 0 KB -