oj.uz

Submission #50340

# Submission time Handle Problem Language Result Execution time Memory
50340 2018-06-10T09:21:54 Z szawinis Palindromes (APIO14_palindrome) C++17
100 / 100
 99 ms 54308 KB 
#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define rofi(i, b, a) fori(int i = int(b); i >= int(a); --i)
#define foreach(it, a) for(auto &it: a)
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define csz(a) int(a.size())
#define load(a, v) fill(begin(a), end(a), v);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e17;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// END TEMPLATE

struct Paltree {
	vector<int> s, len, link, cnt, deg;
	vector<vector<int> > nxt;
	int last = 0;
	Paltree() {
		len.pb(0), len.pb(-1);
		link.pb(1), link.pb(1);
		nxt.pb(vector<int>(26)), nxt.pb(vector<int>(26));
		cnt.pb(0), cnt.pb(0);
		deg.pb(0), deg.pb(0); // not actually 0 but who cares
	}
	int get_link(int v) {
		while(csz(s) - len[v] - 2 < 0 || s.back() != s[csz(s) - len[v] - 2])
			v = link[v];
		return v;
	}
	void update(int c) {
		s.pb(c);
		last = get_link(last);
		if(!nxt[last][c]) {
			len.pb(len[last] + 2);
			int strict_link = nxt[get_link(link[last])][c];
			link.pb(strict_link);
			nxt.pb(vector<int>(26));
			nxt[last][c] = csz(nxt) - 1;
			// cout << "strict link" << strict_link << endl;
			
			// queries
			cnt.pb(1);
			deg.pb(0);
			++deg[strict_link];
		} else ++cnt[nxt[last][c]];
		last = nxt[last][c];
	}
};

int n;
string s;
Paltree t;
ll ans;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	n = s.length();
	fori(i, 0, n-1) t.update(s[i] - 'a');
	queue<int> q;
	fori(i, 0, t.nxt.size()-1) if(!t.deg[i]) q.push(i);
	//
	// fori(i, 0, csz(t.nxt) - 1) cout << t.deg[i] << ' ';
	// cout << endl;
	//
	while(!q.empty()) {
		int i = q.front();
		q.pop();
		ans = max(1ll * t.len[i] * t.cnt[i], ans);
		// cout << i << ' ' << t.len[i] << ' ' << t.cnt[i] << endl;
		t.cnt[t.link[i]] += t.cnt[i];
		--t.deg[t.link[i]];
		if(!t.deg[t.link[i]]) q.push(t.link[i]);
	}
	cout << ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 2 ms 684 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 764 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 816 KB Output is correct
11 Correct 2 ms 832 KB Output is correct
12 Correct 2 ms 892 KB Output is correct
13 Correct 2 ms 896 KB Output is correct
14 Correct 3 ms 900 KB Output is correct
15 Correct 2 ms 904 KB Output is correct
16 Correct 2 ms 928 KB Output is correct
17 Correct 2 ms 1040 KB Output is correct
18 Correct 2 ms 1040 KB Output is correct
19 Correct 2 ms 1040 KB Output is correct
20 Correct 2 ms 1040 KB Output is correct
21 Correct 2 ms 1040 KB Output is correct
22 Correct 2 ms 1040 KB Output is correct
23 Correct 2 ms 1056 KB Output is correct
24 Correct 2 ms 1056 KB Output is correct
25 Correct 2 ms 1056 KB Output is correct
26 Correct 2 ms 1064 KB Output is correct
27 Correct 2 ms 1068 KB Output is correct
28 Correct 2 ms 1068 KB Output is correct
29 Correct 2 ms 1068 KB Output is correct
30 Correct 2 ms 1068 KB Output is correct
31 Correct 2 ms 1068 KB Output is correct
32 Correct 2 ms 1068 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1252 KB Output is correct
2 Correct 2 ms 1252 KB Output is correct
3 Correct 2 ms 1252 KB Output is correct
4 Correct 2 ms 1256 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 3 ms 1264 KB Output is correct
7 Correct 2 ms 1268 KB Output is correct
8 Correct 2 ms 1272 KB Output is correct
9 Correct 2 ms 1276 KB Output is correct
10 Correct 2 ms 1276 KB Output is correct
11 Correct 2 ms 1276 KB Output is correct
12 Correct 2 ms 1288 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2884 KB Output is correct
2 Correct 5 ms 2900 KB Output is correct
3 Correct 5 ms 2928 KB Output is correct
4 Correct 5 ms 2956 KB Output is correct
5 Correct 5 ms 2964 KB Output is correct
6 Correct 5 ms 2996 KB Output is correct
7 Correct 5 ms 3024 KB Output is correct
8 Correct 3 ms 3024 KB Output is correct
9 Correct 2 ms 3024 KB Output is correct
10 Correct 3 ms 3024 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17008 KB Output is correct
2 Correct 27 ms 17124 KB Output is correct
3 Correct 28 ms 17208 KB Output is correct
4 Correct 31 ms 17460 KB Output is correct
5 Correct 32 ms 17680 KB Output is correct
6 Correct 25 ms 17680 KB Output is correct
7 Correct 26 ms 17680 KB Output is correct
8 Correct 6 ms 17680 KB Output is correct
9 Correct 11 ms 17680 KB Output is correct
10 Correct 24 ms 17680 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 51356 KB Output is correct
2 Correct 86 ms 52672 KB Output is correct
3 Correct 83 ms 52672 KB Output is correct
4 Correct 88 ms 52672 KB Output is correct
5 Correct 99 ms 52672 KB Output is correct
6 Correct 88 ms 52956 KB Output is correct
7 Correct 92 ms 52956 KB Output is correct
8 Correct 11 ms 52956 KB Output is correct
9 Correct 11 ms 52956 KB Output is correct
10 Correct 69 ms 52956 KB Output is correct
11 Correct 82 ms 54308 KB Output is correct
12 Correct 16 ms 54308 KB Output is correct