Submission #924739

#	Time	Username	Problem	Language	Result	Execution time	Memory
924739		arneves	Palindromes (APIO14_palindrome)	C++17	0 / 100	5 ms	5304 KiB

palindrome

/*
           ______  _____  _______ _     _ _______ __   _  _____  _  _  _
          |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
          |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
        
        
                   .      .           .      .           .      .    
                   _\/  \/_           _\/  \/_           _\/  \/_    
                    _\/\/_             _\/\/_             _\/\/_     
                _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 
                 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  
                    _/\/\_             _/\/\_             _/\/\_     
                    /\  /\             /\  /\             /\  /\     
                   '      '           '      '           '      '    
        
*/

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define f first
#define s second
#define rep(i, a, b) for(int i = a; i < (b); ++i)

void banana(string nome=""){
	cin.tie(0); ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(12);
	if(nome.size()){
		freopen((nome+".txt").c_str(),"r",stdin);
		freopen((nome+"_in"+".txt").c_str(),"w",stdout);
	}
}

string yon(ll ans){
	return ans?"YES":"NO";
}

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>

//const int MX=1200010;
const ll MX=100;

struct SuffixTree {
	enum { N = MX, ALPHA = 28 }; // N ~ 2*maxlen+10
	int toi(char c) { return c - 'a'; }
	string a; // v = cur node, q = cur position
	int t[N][ALPHA],l[N],r[N],p[N],s[N],v=0,q=0,m=2;
	
	void ukkadd(int i, int c) {
		suff:
		if (r[v]<=q) {
			if (t[v][c]==-1) { t[v][c]=m; l[m]=i;
				p[m++]=v; v=s[v]; q=r[v]; goto suff; }
			v=t[v][c]; q=l[v];
		}
		if (q==-1 || c==toi(a[q])) q++; else {
			l[m+1]=i; p[m+1]=m; l[m]=l[v]; r[m]=q;
			p[m]=p[v]; t[m][c]=m+1; t[m][toi(a[q])]=v;
			l[v]=q; p[v]=m; t[p[m]][toi(a[l[m]])]=m;
			v=s[p[m]]; q=l[m];
			while (q<r[m]) { v=t[v][toi(a[q])]; q+=r[v]-l[v]; }
			if (q==r[m]) s[m]=v; else s[m]=m+2;
			q=r[v]-(q-r[m]); m+=2; goto suff;
		}
	}
	
	SuffixTree(string a_) : a(a_) {
		fill(r,r+N,sz(a));
		memset(s, -1, sizeof s);
		memset(t, -1, sizeof t);
		fill(t[1],t[1]+ALPHA,0);
		s[0] = 1; l[0] = l[1] = -1; r[0] = r[1] = p[0] = p[1] = 0;
		rep(i,0,sz(a)) ukkadd(i, toi(a[i]));
	}
};

void caso_teste(){
	
	string str; cin>>str;
	ll n=str.size();
	string rev=str;
	reverse(all(rev));
	str+=((char)('a'+26));
	str+=rev;
	str+=((char)('a'+27));
	
	SuffixTree st(str);
	vector<set<ll>> v(MX);
	vector<ll> count(MX, 0);
	vector<ll> str_depth(MX, 0);
	
	ll cur=0;
	
	auto dfs = [&](auto&& self, ll s, ll par) -> void {
		ll leaf=1;
		for(ll i=0; i<28; i++) if(st.t[s][i]!=-1) leaf=0;
		if(leaf){
			assert(str[st.r[s]-1]==((char)('a'+27)));
			ll k=str_depth[s];
			if(k!=1 && k!=n+2){
				if(k<n+2) k-=2;
				else k-=(n+3), k=n-k-1-par;
				v[s].insert(k);
			}
		}
		for(ll i=0; i<28; i++){
			if(st.t[s][i]!=-1){
				ll y=st.t[s][i];
				str_depth[y]=str_depth[s]+st.r[y]-st.l[y];
				self(self, y, par);
				count[s]+=count[y];
				if(v[y].size()>v[s].size()) swap(v[y], v[s]);
				
				for(ll u: v[y]){
					if(v[s].find(u)!=v[s].end()) v[s].erase(u), count[s]++;
					else v[s].insert(u);
				}
			}
		}
		
		cur=max(cur, count[s]*(2*str_depth[s]-(1-par)));
	};
	
	dfs(dfs, 0, 0);
	
	v.assign(MX, set<ll>());
	count.assign(MX, 0);
	str_depth.assign(MX, 0);
	
	dfs(dfs, 0, 1);
	
	cout<<cur<<'\n';
}

int main(){
	
	banana();
	
	int n_casos=1; //cin>>n_casos;
	
	while(n_casos--) caso_teste();
}

Compilation message (stderr)

palindrome.cpp: In function 'void banana(std::string)':
palindrome.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   freopen((nome+".txt").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   freopen((nome+"_in"+".txt").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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