Submission #138028

#	Time	Username	Problem	Language	Result	Execution time	Memory
138028		CaroLinda	Palindromes (APIO14_palindrome)	C++14	92 / 100	205 ms	104160 KiB

palindrome

#include <bits/stdc++.h>

#define debug 
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 6e5+1 ;
const int ALF= 35 ;

using namespace std ;


struct Trie
{

	int nodes ;
	int trie[MAXN][ALF] , lazy[MAXN] , parent[MAXN] ;
	ll ans ;

	Trie()
	{

		memset(trie, 0, sizeof trie) ;
		memset(lazy,0,sizeof lazy) ;
		parent[0] = 0 ;
		nodes = 0 ;
		ans = 0 ;

	}

	// The interval becomes [l,r]
	int add( char str[] , int l , int r , int address )
	{

		int cur = address ;

		for(int i = l ; i <= r ; i++ )
		{

			char c = str[i] - 'a' ;

			if( trie[cur][c] == 0 )
			{
				trie[cur][c] = ++ nodes ;
				parent[ nodes ] = cur ;
			}

			cur = trie[cur][c] ;

		}

		lazy[cur] ++ ;

		return cur ;

	}

	int goUp( int address, int qtd )
	{


		lp(i,0,qtd) address = parent[address] ;

		return address ;

	}


	ll dfs( int cur , int depth , bool what )
	{


		ll tempAns = lazy[cur] ;

		lp(i,0,30)
			if( trie[cur][i] != 0 )
				tempAns += dfs(trie[cur][i] , depth+1 , what ) ;

		ll multiplier = ( what ?  ( depth/2 ) * 2 : ( ( (depth-1)/2 )*2 + 1 ) ) ;

		ans = max( ans , tempAns * multiplier ) ;

		debug("%d -> %lld %lld\n" , cur , tempAns , multiplier ) ;

		return tempAns ;

	}


} ;

int n ;

int p[MAXN] , myAd[MAXN] ;

Trie trie ;

char str[MAXN] ;

// --------------------------

void findAns()
{

	
	//If I want an odd palindrome
	lp(i,0,27)
		if( trie.trie[0][i] != 0 )
			trie.dfs( trie.trie[0][i] , 1 , 0 ) ;


	//If I want an even palindrome
	trie.dfs( trie.trie[0][27] , 1 , 1 ) ;


}

void manacher()
{

	int center = 0 , right = -1 ;

	lp(i,0,n)
	{

		int rad= 0 , last = 0 , ant = i ;

		if( i <= right )
		{
			rad = min( p[2*center-i] , right - i + 1 ) ;
			last = trie.goUp( myAd[2*center-i] , p[2*center-i] - rad ) ;
			ant = rad + i ;
		}


		while( i - rad >= 0 && i + rad < n && str[i-rad] == str[i+rad] )
			{ rad ++ ; }

		myAd[i] = trie.add(str, ant , i+rad-1 , last ) ;
		p[i] = rad ;

		debug("With center %d, we have a ratio of %d and the last I used was %d and it became %d\n\n" , i , rad  , last , myAd[i]) ;

		if( i+rad-1 > right )
		{
			center = i ;
			right = i+rad-1 ;
		}

	}


}



int main()
{

	char difStr[MAXN] ;

	scanf(" %s" , difStr ) ;

	n = strlen(difStr)*2 - 1 ;

	lp(i,0,n)
	{

		if( i%2 == 0 ) str[i] = difStr[i/2] ;

		else str[i] = '|' ;

	}

	manacher() ;

	findAns() ;

	printf("%lld\n" , trie.ans ) ;

}

Compilation message (stderr)

palindrome.cpp: In member function 'int Trie::add(char*, int, int, int)':
palindrome.cpp:47:19: warning: array subscript has type 'char' [-Wchar-subscripts]
    if( trie[cur][c] == 0 )
                   ^
palindrome.cpp:49:16: warning: array subscript has type 'char' [-Wchar-subscripts]
     trie[cur][c] = ++ nodes ;
                ^
palindrome.cpp:53:21: warning: array subscript has type 'char' [-Wchar-subscripts]
    cur = trie[cur][c] ;
                     ^
palindrome.cpp: In member function 'long long int Trie::dfs(int, int, bool)':
palindrome.cpp:88:31: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("%d -> %lld %lld\n" , cur , tempAns , multiplier ) ;
                               ^~~
palindrome.cpp:88:37: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("%d -> %lld %lld\n" , cur , tempAns , multiplier ) ;
                                     ^~~~~~~
palindrome.cpp:88:47: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("%d -> %lld %lld\n" , cur , tempAns , multiplier ) ;
                                               ^~~~~~~~~~
palindrome.cpp: In function 'void manacher()':
palindrome.cpp:147:99: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("With center %d, we have a ratio of %d and the last I used was %d and it became %d\n\n" , i , rad  , last , myAd[i]) ;
                                                                                                   ^
palindrome.cpp:147:103: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("With center %d, we have a ratio of %d and the last I used was %d and it became %d\n\n" , i , rad  , last , myAd[i]) ;
                                                                                                       ^~~
palindrome.cpp:147:110: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("With center %d, we have a ratio of %d and the last I used was %d and it became %d\n\n" , i , rad  , last , myAd[i]) ;
                                                                                                              ^~~~
palindrome.cpp:147:123: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("With center %d, we have a ratio of %d and the last I used was %d and it became %d\n\n" , i , rad  , last , myAd[i]) ;
                                                                                                                           ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:167:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s" , difStr ) ;
  ~~~~~^~~~~~~~~~~~~~~~~

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