oj.uz

Submission #367135

# Submission time Handle Problem Language Result Execution time Memory
367135 2021-02-16T10:42:22 Z alireza_kaviani Palindromes (APIO14_palindrome) C++11
100 / 100
 85 ms 65524 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 3e5 + 10;
const ll LOG = 26;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , palPrv , nxt[MAXN][LOG] , par[MAXN] , len[MAXN] , val[MAXN];
ll ans = 0;
vector<int> adj[MAXN];
string s;

void DFS(int v){
	for(int u : adj[v]){
//		cout << v << sep << u << endl;
		DFS(u);
		val[v] += val[u];
	}
	ans = max(ans , 1ll * val[v] * len[v]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> s; n = SZ(s);
	len[0] = -1; len[1] = 0;
	par[1] = 0; palPrv = 1;
	adj[0].push_back(1);
	for(int i = 0 ; i < n ; i++){
		int prv = palPrv , ch = s[i] - 97;
//		cout << i << sep << prv << endl;
		while(1){
			int k = len[prv];
//			cout << i << sep << prv << sep << k << endl;
			if(0 <= i - k - 1 && s[i] == s[i - k - 1])	break;
			prv = par[prv];
		}
//		cout << i << sep << prv << endl;
		if(nxt[prv][ch] != 0){
			palPrv = nxt[prv][ch];
			val[palPrv]++;
			continue;
		}
		int cur = i + 2;
		//cout << prv << sep << cur << endl;
		palPrv = cur; val[cur]++;
		nxt[prv][ch] = cur;
		len[cur] = len[prv] + 2;
		if(len[cur] == 1){
			par[cur] = 1;
			adj[1].push_back(cur);
			continue;
		}
		while(1){
			prv = par[prv];
			int k = len[prv];
			if(0 <= i - k - 1 && s[i] == s[i - k - 1])	break;
		}
		par[cur] = nxt[prv][ch];
		adj[nxt[prv][ch]].push_back(cur);
	}
	DFS(0);
	cout << ans << endl;

    return 0;
}
/*

*/

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9068 KB Output is correct
2 Correct 7 ms 9068 KB Output is correct
3 Correct 7 ms 9324 KB Output is correct
4 Correct 7 ms 9324 KB Output is correct
5 Correct 7 ms 8684 KB Output is correct
6 Correct 7 ms 8812 KB Output is correct
7 Correct 7 ms 8940 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 7 ms 7660 KB Output is correct
10 Correct 7 ms 8300 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24428 KB Output is correct
2 Correct 24 ms 23404 KB Output is correct
3 Correct 25 ms 26732 KB Output is correct
4 Correct 29 ms 25068 KB Output is correct
5 Correct 28 ms 20224 KB Output is correct
6 Correct 19 ms 17900 KB Output is correct
7 Correct 21 ms 20204 KB Output is correct
8 Correct 9 ms 9452 KB Output is correct
9 Correct 13 ms 13292 KB Output is correct
10 Correct 21 ms 18284 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 58580 KB Output is correct
2 Correct 56 ms 53364 KB Output is correct
3 Correct 64 ms 65524 KB Output is correct
4 Correct 57 ms 56564 KB Output is correct
5 Correct 85 ms 46452 KB Output is correct
6 Correct 53 ms 48372 KB Output is correct
7 Correct 50 ms 45044 KB Output is correct
8 Correct 16 ms 12680 KB Output is correct
9 Correct 14 ms 12532 KB Output is correct
10 Correct 66 ms 39540 KB Output is correct
11 Correct 60 ms 53748 KB Output is correct
12 Correct 20 ms 17524 KB Output is correct