| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547975 |
2022-04-12T05:31:37 Z |
Jomnoi |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
11308 KB |
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int MAX_N = 5e4 + 10;
const int P = 31;
const int MOD = 1e9 + 9;
int N;
char S[MAX_N];
vector <int> graph[MAX_N];
long long expo[MAX_N];
class CentroidDecomposition {
private :
char cen;
int max_len;
long long H[MAX_N], rH[MAX_N];
int sz[MAX_N], depth[MAX_N], parent[MAX_N][16];
bool processed[MAX_N];
vector <int> centroid, tmp;
unordered_set <long long> mp;
public :
int get_size(const int &u, const int &p) {
sz[u] = 1;
for(auto v : graph[u]) {
if(v != p and processed[v] == false) {
sz[u] += get_size(v, u);
}
}
return sz[u];
}
int get_centroid(const int &u, const int &p, const int &n) {
for(auto v : graph[u]) {
if(v != p and processed[v] == false and sz[v] > n / 2) {
return get_centroid(v, u, n);
}
}
return u;
}
void build_centroid() {
depth[0] = -1;
queue <int> q;
q.push(1);
while(!q.empty()) {
int c = q.front();
q.pop();
c = get_centroid(c, -1, get_size(c, -1));
processed[c] = true;
centroid.push_back(c);
for(auto v : graph[c]) {
if(processed[v] == false) {
q.push(v);
}
}
}
}
int jump(const int &a, const int &k) {
int u = a;
for(int i = 0; i < 16; i++) {
if(k & (1<<i)) {
u = parent[u][i];
}
}
return u;
}
bool preprocess(const int &u, const int &p) {
depth[u] = depth[p] + 1;
if(depth[u] > max_len) {
return false;
}
parent[u][0] = p;
for(int i = 1; i < 16; i++) {
parent[u][i] = parent[parent[u][i - 1]][i - 1];
}
H[u] = (H[p] * P + S[u]) % MOD;
rH[u] = (rH[p] + S[u] * expo[depth[u]]) % MOD;
if(max_len == depth[u] + 1 and H[u] == rH[u]) {
return true;
}
for(auto v : graph[u]) {
if(v != p and processed[v] == false and preprocess(v, u) == true) {
return true;
}
}
return false;
}
bool dfs(const int &u, const int &p) {
if(depth[u] > max_len) {
return false;
}
// before substring + palindrome in current side + substring
if(depth[u] >= max_len / 2) {
int v = jump(u, max_len - depth[u] - 2);
if(H[parent[v][0]] == rH[parent[v][0]] and mp.count(((H[u] - (H[parent[v][0]] - cen) * expo[max_len - depth[u] - 1]) % MOD + MOD) % MOD)) {
return true;
}
}
tmp.push_back(H[u]);
for(auto v : graph[u]) {
if(v != p and processed[v] == false and dfs(v, u) == true) {
return true;
}
}
return false;
}
bool solve(const int &len) {
if(len <= 1) {
return true;
}
max_len = len;
fill(processed + 1, processed + N + 1, false);
for(auto c : centroid) {
cen = S[c];
depth[c] = 0;
processed[c] = true;
H[c] = rH[c] = cen;
// Preprocess (Some operation that process once)
for(auto v : graph[c]) {
if(processed[v] == false and preprocess(v, c) == true) {
return true;
}
}
// Left to right
mp.clear();
for(auto v : graph[c]) {
if(processed[v] == true) {
continue;
}
tmp.clear();
if(dfs(v, c) == true) {
return true;
}
for(auto x : tmp) {
mp.insert(x);
}
}
// Right to left
mp.clear();
reverse(graph[c].begin(), graph[c].end());
for(auto v : graph[c]) {
if(processed[v] == true) {
continue;
}
tmp.clear();
if(dfs(v, c) == true) {
return true;
}
for(auto x : tmp) {
mp.insert(x);
}
}
}
return false;
}
}ct;
int main() {
int l, r, mid, res, ans = 0;
scanf(" %d %s", &N, S + 1);
for(int i = 1; i <= N - 1; i++) {
int A, B;
scanf(" %d %d", &A, &B);
graph[A].push_back(B);
graph[B].push_back(A);
}
// Preprocess
expo[0] = 1;
for(int i = 1; i < MAX_N; i++) {
expo[i] = (expo[i - 1] * P) % MOD;
}
for(int i = 1; i <= N; i++) {
S[i] = S[i] - 'a' + 1;
}
ct.build_centroid();
// Compute even length
l = 0, r = N / 2, res = 0;
while(l <= r) {
mid = (l + r) / 2;
if(ct.solve(2 * mid) == true) {
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
ans = max(ans, 2 * res);
// Compute odd length
l = 0, r = N / 2, res = 0;
while(l <= r) {
mid = (l + r) / 2;
if(ct.solve(2 * mid + 1) == true) {
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
ans = max(ans, 2 * res + 1);
printf("%d", ans);
return 0;
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | scanf(" %d %s", &N, S + 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
lampice.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf(" %d %d", &A, &B);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2020 KB |
Output is correct |
| 3 |
Correct |
54 ms |
2148 KB |
Output is correct |
| 4 |
Correct |
48 ms |
2144 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1872 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
11308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5025 ms |
10904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2020 KB |
Output is correct |
| 3 |
Correct |
54 ms |
2148 KB |
Output is correct |
| 4 |
Correct |
48 ms |
2144 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1872 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 8 |
Execution timed out |
5067 ms |
11308 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
