| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547971 |
2022-04-12T05:21:50 Z |
Jomnoi |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
12012 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;
char S[MAX_N];
vector <int> graph[MAX_N];
long long expo[MAX_N];
class CentroidDecomposition {
private :
int max_len;
long long H[MAX_N], rH[MAX_N];
int sz[MAX_N], depth[MAX_N], parent[MAX_N][16];
bitset <MAX_N> processed;
vector <int> centroid, tmp;
unordered_set <int> 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() {
queue <int> q;
q.push(1);
while(!q.empty()) {
int u = q.front();
q.pop();
int c = get_centroid(u, -1, get_size(u, -1));
processed[c] = true;
centroid.push_back(c);
for(auto v : graph[c]) {
if(processed[v] == false) {
q.push(v);
}
}
}
}
int jump(int u, const int &k) {
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, const int &lvl) {
depth[u] = lvl;
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[lvl]) % MOD;
if(max_len == lvl + 1 and H[u] == rH[u]) {
return true;
}
for(auto v : graph[u]) {
if(v != p and processed[v] == false and preprocess(v, u, lvl + 1) == true) {
return true;
}
}
return false;
}
int cal(const int &l, const int &r, const int &c) {
long long res = ((H[r] - H[parent[l][0]] * expo[max_len - depth[r] - 1]) % MOD + MOD) % MOD;
res = (res + expo[max_len - depth[r] - 1] * S[c]) % MOD;
return res;
}
bool dfs(const int &u, const int &p, const int &c) {
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(cal(v, u, c))) {
return true;
}
}
tmp.push_back(H[u]);
for(auto v : graph[u]) {
if(v != p and processed[v] == false and dfs(v, u, c) == true) {
return true;
}
}
return false;
}
bool solve(const int &len) {
if(len <= 1) {
return true;
}
max_len = len;
processed = 0;
for(auto c : centroid) {
processed[c] = true;
H[c] = rH[c] = S[c];
// Preprocess (Some operation that process once)
for(auto v : graph[c]) {
if(processed[v] == false and preprocess(v, c, 1) == true) {
return true;
}
}
// Left to right
mp.clear();
for(auto v : graph[c]) {
if(processed[v] == true) {
continue;
}
tmp.clear();
if(dfs(v, c, c) == true) {
return true;
}
for(auto x : tmp) {
mp.insert(x);
}
}
// Right to left
mp.clear();
for(int i = graph[c].size() - 1; i >= 0; i--) {
int v = graph[c][i];
if(processed[v] == true) {
continue;
}
tmp.clear();
if(dfs(v, c, c) == true) {
return true;
}
for(auto x : tmp) {
mp.insert(x);
}
}
}
return false;
}
}ct;
int main() {
int N, 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 |
5 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2008 KB |
Output is correct |
| 3 |
Correct |
58 ms |
2144 KB |
Output is correct |
| 4 |
Correct |
53 ms |
2220 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5044 ms |
12012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5052 ms |
11432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2008 KB |
Output is correct |
| 3 |
Correct |
58 ms |
2144 KB |
Output is correct |
| 4 |
Correct |
53 ms |
2220 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 8 |
Execution timed out |
5044 ms |
12012 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
