답안 #32156 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32156	2017-09-28T03:14:23 Z	minimario	회문 (APIO14_palindrome)	C++14	100 / 100	126 ms	67116 KB

palindrome

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 300005;
 
struct node {
	int len;
	int next[26];
	int suff;
	int ct;
};
 
node t[MAX];
int i = 0;
int ans = 0;
 
void roots() {
	t[0].len = -1; t[0].suff = 0;
	t[1].len = 0; t[1].suff = 0;
}
 
int ct = 2;
int maxsuff = 1;
string s;
void add(int pos) {
	int j = maxsuff;
	int c = s[pos] - 'a'; // the character
	while (s[pos-t[j].len-1] != s[pos]) {
		j = t[j].suff;
	}
	if (t[j].next[c] == 0) {
		t[j].next[c] = ct;
		t[ct].len = t[j].len + 2;
		ct++;
	}
	maxsuff = t[j].next[c];
	if (j == 0) {
		t[maxsuff].suff = 1;
	}
	else {
		j = t[j].suff;
		while (s[pos-t[j].len-1] != s[pos]) {
			j = t[j].suff; 
		}
		if (t[j].next[c] == 0) {
			t[j].next[c] = ct;
			t[ct].len = t[j].len + 2;
			ct++;
		}
		t[maxsuff].suff = t[j].next[c];
	}
	t[maxsuff].ct++;
}
 
bool v[MAX];
 
vector<int> g[MAX];
void create() {
	for (int i=2; i<MAX; i++) {
		if (t[i].suff > 1) {
			g[t[i].suff].push_back(i);
		}
	}
}
void dfs(int u) {
	v[u] = true;
	for (int i : g[u]) {
		dfs(i);
		t[u].ct += t[i].ct;
	}
}
 
int main() {
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> s;
	s = " " + s;
	roots();
	for (int i=1; i<s.length(); i++) {
		add(i);
	}
	v[0] = v[1] = true;
	create();
	for (int i=2; i<MAX; i++) {
		if (!v[i]) { dfs(i); }
	}
	long long maxi = 0;
	for (int i=2; i<MAX; i++) {
		maxi = max(maxi, (long long)t[i].len * (long long)t[i].ct);
	}
	cout << maxi << endl;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<s.length(); i++) {
                 ^

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	43484 KB	Output is correct
2	Correct	6 ms	43484 KB	Output is correct
3	Correct	0 ms	43484 KB	Output is correct
4	Correct	3 ms	43484 KB	Output is correct
5	Correct	6 ms	43484 KB	Output is correct
6	Correct	6 ms	43484 KB	Output is correct
7	Correct	3 ms	43484 KB	Output is correct
8	Correct	3 ms	43484 KB	Output is correct
9	Correct	3 ms	43484 KB	Output is correct
10	Correct	6 ms	43484 KB	Output is correct
11	Correct	3 ms	43484 KB	Output is correct
12	Correct	6 ms	43484 KB	Output is correct
13	Correct	9 ms	43484 KB	Output is correct
14	Correct	3 ms	43484 KB	Output is correct
15	Correct	6 ms	43484 KB	Output is correct
16	Correct	6 ms	43484 KB	Output is correct
17	Correct	6 ms	43484 KB	Output is correct
18	Correct	3 ms	43484 KB	Output is correct
19	Correct	6 ms	43484 KB	Output is correct
20	Correct	9 ms	43484 KB	Output is correct
21	Correct	6 ms	43484 KB	Output is correct
22	Correct	3 ms	43484 KB	Output is correct
23	Correct	3 ms	43484 KB	Output is correct
24	Correct	3 ms	43484 KB	Output is correct
25	Correct	6 ms	43484 KB	Output is correct
26	Correct	3 ms	43484 KB	Output is correct
27	Correct	3 ms	43484 KB	Output is correct
28	Correct	0 ms	43484 KB	Output is correct
29	Correct	6 ms	43484 KB	Output is correct
30	Correct	6 ms	43484 KB	Output is correct
31	Correct	0 ms	43484 KB	Output is correct
32	Correct	6 ms	43484 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	43484 KB	Output is correct
2	Correct	6 ms	43484 KB	Output is correct
3	Correct	6 ms	43484 KB	Output is correct
4	Correct	6 ms	43484 KB	Output is correct
5	Correct	6 ms	43484 KB	Output is correct
6	Correct	6 ms	43484 KB	Output is correct
7	Correct	13 ms	43484 KB	Output is correct
8	Correct	3 ms	43484 KB	Output is correct
9	Correct	3 ms	43484 KB	Output is correct
10	Correct	6 ms	43484 KB	Output is correct
11	Correct	3 ms	43484 KB	Output is correct
12	Correct	6 ms	43484 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	43856 KB	Output is correct
2	Correct	0 ms	43788 KB	Output is correct
3	Correct	3 ms	44088 KB	Output is correct
4	Correct	6 ms	44020 KB	Output is correct
5	Correct	6 ms	43616 KB	Output is correct
6	Correct	6 ms	43616 KB	Output is correct
7	Correct	3 ms	43748 KB	Output is correct
8	Correct	6 ms	43484 KB	Output is correct
9	Correct	9 ms	43484 KB	Output is correct
10	Correct	6 ms	43484 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	48864 KB	Output is correct
2	Correct	19 ms	47844 KB	Output is correct
3	Correct	13 ms	51212 KB	Output is correct
4	Correct	16 ms	49508 KB	Output is correct
5	Correct	26 ms	44668 KB	Output is correct
6	Correct	23 ms	45392 KB	Output is correct
7	Correct	16 ms	46452 KB	Output is correct
8	Correct	9 ms	43636 KB	Output is correct
9	Correct	6 ms	45196 KB	Output is correct
10	Correct	13 ms	44536 KB	Output is correct

Subtask #5
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	60092 KB	Output is correct
2	Correct	63 ms	55044 KB	Output is correct
3	Correct	46 ms	67116 KB	Output is correct
4	Correct	46 ms	58156 KB	Output is correct
5	Correct	126 ms	48168 KB	Output is correct
6	Correct	49 ms	53816 KB	Output is correct
7	Correct	33 ms	52184 KB	Output is correct
8	Correct	6 ms	44324 KB	Output is correct
9	Correct	9 ms	44324 KB	Output is correct
10	Correct	119 ms	47244 KB	Output is correct
11	Correct	86 ms	55400 KB	Output is correct
12	Correct	9 ms	45756 KB	Output is correct

답안 #32156

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