oj.uz

Submission #171655

# Submission time Handle Problem Language Result Execution time Memory
171655 2019-12-29T13:43:40 Z njrafi Palindromes (APIO14_palindrome) C++14
73 / 100
 34 ms 12692 KB 
#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#define gc getchar
#define pc putchar
#else
#define gc getchar_unlocked
#define pc putchar_unlocked
#endif

using namespace std;

#define vi vector<int>
#define si set<int>
#define vs vector<string>
#define pii pair<int,int>
#define vpi vector<pii>
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define mpi map<int,int>
#define i64 long long int
#define endl '\n'
#define pi acos(-1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf INT_MAX/2
#define infll LLONG_MAX/3
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define eps 1e-8
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define dbg(i) printf("yo %d\n", i)
#define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define sqr(a) (a) * (a)
#define clr clear()
#define CASE(a) printf("Case #%d: ",a)

//int dx[] = {0,1,0,-1,1,1,-1,-1};
//int dy[] = {1,0,-1,0,1,-1,-1,1};


//i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}

//inline void fastRead(int *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}

//inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}

//i64 bigmod(i64 num,i64 n){if(n==0)return 1;i64 x=bigmod(num,n/2);x=x*x%mod;if(n%2==1)x=x*num%mod;return x;}

//i64 modinverse(i64 num){return bigmod(num,mod-2)%mod;}

//i64 po(i64 a,i64 b){i64 ans=1;while(b--)ans *= a;return ans;}

//i64 ncr(i64 n,i64 r){if(n==r)return 1;if(r==1)return n;if(dp[n][r]!=-1)return dp[n][r];return dp[n][r]=ncr(n-1,r)+ncr(n-1,r-1);}


// bit manipulations

//bool checkbit(int mask,int bit){return mask & (1<<bit);}

//int setbit(int mask,int bit){ return mask  (1<<bit) ; }

//int clearbit(int mask,int bit){return mask & ~(1<<bit);}

//int togglebit(int mask,int bit){return mask ^ (1<<bit);}



// Code from https://rezwanarefin01.github.io/posts/palindromic-tree-01/

/*
Concept:
aba -> tree[nodeNumber][c] means -> cabac , adding c in both side
for odd length, define one root and consider the length -1
Suffix Link: biggest proper suffix ( length < string length) which is also a palindrome
if no proper suffix , link to root with length 0
length 0 root links back to length -1 root
length -1 root links to own node

tree[node][character] -> trie info
len[node] -> length of the node
link[node] -> suffix link
last = holds the max palindrome suffix of the processed prefix till now
endAt[node] -> total palindrome ends at i

fact 1: N length string can only have N distinct palindrome
fact 2: Palindrome tree holds all distinct palindrome
fact 3: number of distinct palindrome = freeNode - 2
fact 4: number of total palindrome = sum of( endsAt[i]) 0 to freeNode
*/

#define mxn 100005
int tree[mxn][26], freeNode;
int len[mxn], link[mxn], last;
string s;

//int endAt[mxn];
int freq[mxn];

void extend(int p) {
	while(s[p - len[last] - 1] != s[p])
		last = link[last];
	int x = link[last], c = s[p] - 'a';
	while(s[p - len[x] - 1] != s[p])
		x = link[x];
	if(!tree[last][c]) {
		tree[last][c] = ++freeNode;
		len[freeNode] = len[last] + 2;
		link[freeNode] = len[freeNode] == 1 ? 2 : tree[x][c];
//		endAt[freeNode] = endAt[link[freeNode]] + 1;
	}
	last = tree[last][c];
	freq[last]++;
}

void ini() {
	mem(tree,0);
	mem(len,0);
	mem(link,0);
//	mem(endAt,0);
	mem(freq,0);
	len[1] = -1, link[1] = 1;
	len[2] = 0, link[2] = 1;
	freeNode = last = 2;
}

void inputAndBuild() {
	ini();
        cin >> s;
        s = "$" + s;
        Fre(i,1,s.sz)
		extend(i);
        for(int i = freeNode ; i > 2 ; i--) freq[link[i]] += freq[i];
}


int main() {

        inputAndBuild();
        i64 ans = 0;
	For(i,freeNode + 1)
		ans = max(ans, (i64)len[i] * freq[i]);
	cout << ans << endl;









	return 0;
}

Compilation message

palindrome.cpp: In function 'void inputAndBuild()':
palindrome.cpp:31:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define Fre(i,a,b) for(int i = a; i < b; i++)
                                     ^
palindrome.cpp:143:9: note: in expansion of macro 'Fre'
         Fre(i,1,s.sz)
         ^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11640 KB Output is correct
2 Correct 12 ms 11640 KB Output is correct
3 Correct 11 ms 11640 KB Output is correct
4 Correct 11 ms 11640 KB Output is correct
5 Correct 12 ms 11640 KB Output is correct
6 Correct 12 ms 11640 KB Output is correct
7 Correct 14 ms 11612 KB Output is correct
8 Correct 14 ms 11616 KB Output is correct
9 Correct 14 ms 11640 KB Output is correct
10 Correct 14 ms 11640 KB Output is correct
11 Correct 14 ms 11640 KB Output is correct
12 Correct 13 ms 11744 KB Output is correct

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12020 KB Output is correct
2 Correct 20 ms 12020 KB Output is correct
3 Correct 20 ms 12024 KB Output is correct
4 Correct 20 ms 12024 KB Output is correct
5 Correct 20 ms 12024 KB Output is correct
6 Correct 20 ms 12028 KB Output is correct
7 Correct 20 ms 12024 KB Output is correct
8 Correct 19 ms 12024 KB Output is correct
9 Correct 19 ms 12024 KB Output is correct
10 Correct 20 ms 12024 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 12692 KB Output isn't correct
2 Halted 0 ms 0 KB -