Submission #439418

#	Time	Username	Problem	Language	Result	Execution time	Memory
439418		keta_tsimakuridze	Palindromes (APIO14_palindrome)	C++14	0 / 100	136 ms	75288 KiB

palindrome

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,n,pos[N],ind[N],lcp[N],mx,sz[N],par[N];
vector<pair<int,pair<int,int> > > y;
vector<pair<pair<int,int>,int>  > c[N],p;
vector<pair<int,int> >x;
string s;
void Sort(){
	for(int i=0;i<p.size();i++){
		c[p[i].f.s].push_back(p[i]);
	}
	p.clear();
	for(int i=0;i<=n;i++){
		for(int j=0;j<c[i].size();j++){
			p.push_back(c[i][j]);
		}
		c[i].clear();
	}
	for(int i=0;i<p.size();i++){
		c[p[i].f.f].push_back(p[i]);
	}
	p.clear();
	for(int i=0;i<=n;i++){
		for(int j=0;j<c[i].size();j++){
			p.push_back(c[i][j]);
		}
		c[i].clear();
	}
}
int find_parent(int u){
	if(par[u] == u) return u;
	return par[u] = find_parent(par[u]);
}
void merge(int u,int v){
	u = find_parent(u);
	v = find_parent(v);
	if(u==v) return;
	if(sz[u] < sz[v]) swap(u,v);
	par[v] = u;
	sz[u] += sz[v];
	mx = max(mx,sz[u]);
}
 main(){
	cin>>s;
	n = s.size();
	s='#'+s;
	for(int i=1;i<=n;i++){
		par[i] = i;
		sz[i] = 1;
		x.push_back({s[i]-'a'+1,i});
	}
	sort(x.begin(),x.end());
	int idx = 0;
	for(int i=0;i<x.size();i++){
		if(!i || x[i].f!=x[i-1].f) idx++;
		ind[x[i].s] = idx; 
	}
	int Lg = log2(n) + 1;
	for(int i=1;i<=Lg;i++) {
		p.clear();
		for(int j=1;j<=n;j++) {
			p.push_back({{ind[j],ind[j+(1<<(i-1))]},j});
		}
		Sort();
		int idx = 0;
		for(int j=0;j<p.size();j++){
			if(!j || p[j].f.f!=p[j-1].f.f || p[j].f.s!=p[j-1].f.s){
				idx++;
			} 
			ind[p[j].s] = idx;
			pos[idx] = p[j].s;
		}
	}
	int cur = 0;
	for(int i=1;i<=n;i++){
		int bef = pos[ind[i] - 1];
		while(max(bef,i) + cur <= n && s[bef+cur] == s[i+cur]) cur++;
		lcp[ind[i]] = cur;

		y.push_back({ cur, {ind[i]-1,ind[i]}});
		if(cur) cur--;
	}
	sort(y.rbegin(),y.rend());
	int ans = n;
	for(int i=0;i<n;i++) {
		merge(y[i].s.f,y[i].s.s);
		ans = max(ans,mx*y[i].f);
	}
	cout<<ans;
	
}

Compilation message (stderr)

palindrome.cpp: In function 'void Sort()':
palindrome.cpp:13:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
palindrome.cpp:18:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int j=0;j<c[i].size();j++){
      |               ~^~~~~~~~~~~~
palindrome.cpp:23:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
palindrome.cpp:28:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int j=0;j<c[i].size();j++){
      |               ~^~~~~~~~~~~~
palindrome.cpp: At global scope:
palindrome.cpp:47:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 |  main(){
      |  ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:58:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~
palindrome.cpp:70:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int j=0;j<p.size();j++){
      |               ~^~~~~~~~~

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