답안 #50340 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50340	2018-06-10T09:21:54 Z	szawinis	회문 (APIO14_palindrome)	C++17	100 / 100	99 ms	54308 KB

palindrome

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #50340

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 27.0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
27.0 / 27.0