| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097964 |
2024-10-08T17:01:55 Z |
f0rizen |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
12452 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
struct BinaryJumps {
static const int lg = 16;
vector<int> d;
vector<vector<int>> up;
BinaryJumps() {}
BinaryJumps(int n) {
d.resize(n);
up.resize(lg, vector<int>(n, -1));
}
void add_leaf(int v, int p) {
d[v] = d[p] + 1;
up[0][v] = p;
for (int i = 1; i < lg; ++i) {
if (up[i - 1][v] != -1) {
up[i][v] = up[i - 1][up[i - 1][v]];
}
}
}
void remove(int v) {
d[v] = 0;
for (int i = 0; i < lg; ++i) {
up[i][v] = -1;
}
}
int la(int v, int k) {
if (k == 0) {
return v;
}
for (int i = lg - 1; i >= 0; --i) {
if (k >= (1 << i)) {
k -= (1 << i);
v = up[i][v];
}
}
return v;
}
};
const int P = 227, mod = 1e9 + 9;
int mul(int a, int b) {
return (a * 1ll * b) % mod;
}
int sub(int a, int b) {
return ((a - b) % mod + mod) % mod;
}
vector<int> pw;
vector<int> a;
vector<vector<int>> g;
BinaryJumps tr;
vector<bool> used;
vector<int> sz;
vector<vector<int>> dp, rdp;
unordered_set<int> st;
void dfs_sz(int v, int p = -1) {
sz[v] = 1;
for (auto u : g[v]) {
if (u != p && !used[u]) {
tr.add_leaf(u, v);
dfs_sz(u, v);
sz[v] += sz[u];
}
}
}
void dfs_dp(int v, int p = -1, int d = 0) {
dp[0][v] = (mul(dp[0][p], P) + a[v]) % mod;
rdp[0][v] = (mul(a[v], pw[d - 1]) + rdp[0][p]) % mod;
dp[1][v] = (mul(dp[1][p], P) + a[v]) % mod;
rdp[1][v] = (mul(a[v], pw[d]) + rdp[1][p]) % mod;
for (auto u : g[v]) {
if (u != p && !used[u]) {
dfs_dp(u, v, d + 1);
}
}
}
bool dfs_ans(int len, int v, int p = -1, int d = 0) {
if (d + 1 == len && dp[1][v] == rdp[1][v]) {
return true;
}
if (len - d - 1 > 0) {
if (2 * d + 2 - len > 0) {
int u = tr.la(v, len - d - 1);
if (dp[1][u] == rdp[1][u]) {
int h = sub(dp[1][v], mul(pw[len - d - 1], dp[1][u]));
if (st.find(h) != st.end()) {
return true;
}
}
} else if (2 * d + 2 - len == 0) {
int h = dp[1][v];
if (st.find(h) != st.end()) {
return true;
}
}
}
for (auto u : g[v]) {
if (u != p && !used[u]) {
if (dfs_ans(len, u, v, d + 1)) {
return true;
}
}
}
return false;
}
void dfs_insert(int v, int p = -1) {
st.insert(dp[0][v]);
for (auto u : g[v]) {
if (u != p && !used[u]) {
dfs_insert(u, v);
}
}
}
void dfs_clear(int v, int p = -1) {
dp[0][v] = 0;
rdp[0][v] = 0;
dp[1][v] = 0;
rdp[1][v] = 0;
for (auto u : g[v]) {
if (u != p && !used[u]) {
dfs_clear(u, v);
tr.remove(u);
}
}
}
int centroid(int v, int p, int n) {
for (auto u : g[v]) {
if (u != p && !used[u]) {
if (sz[u] * 2 > n) {
return centroid(u, v, n);
}
}
}
return v;
}
bool ok = false;
void build(int v, int len) {
dfs_sz(v);
if (len == 1) {
ok = true;
}
dp[1][v] = a[v];
rdp[1][v] = a[v];
for (auto u : g[v]) {
if (!used[u]) {
dfs_dp(u, v, 1);
}
}
for (auto u : g[v]) {
if (!used[u]) {
if (dfs_ans(len, u, v, 1)) {
ok = true;
}
dfs_insert(u, v);
}
}
st.clear();
for (int i = (int) g[v].size() - 1; i >= 0; --i) {
int u = g[v][i];
if (!used[u]) {
if (dfs_ans(len, u, v, 1)) {
ok = true;
}
dfs_insert(u, v);
}
}
st.clear();
dfs_clear(v);
used[v] = 1;
for (auto u : g[v]) {
if (!used[u]) {
build(centroid(u, v, sz[u]), len);
}
}
}
int32_t main() {
#ifdef LOCAL
freopen("/tmp/input.txt", "r", stdin);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int n;
cin >> n;
pw.resize(n);
pw[0] = 1;
for (int i = 1; i < n; ++i) {
pw[i] = mul(pw[i - 1], P);
}
a.resize(n);
for (int i = 0; i < n; ++i) {
char c;
cin >> c;
a[i] = c - 'a' + 1;
}
g.resize(n);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
tr = BinaryJumps(n);
used.resize(n);
sz.resize(n);
dp.resize(2, vector<int>(n));
rdp.resize(2, vector<int>(n));
dfs_sz(0);
int c = centroid(0, -1, sz[0]);
int ans = 0;
{
int l = 0, r = n / 2 + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (2 * mid > n) {
r = mid;
continue;
}
ok = false;
fill(used.begin(), used.end(), 0);
build(c, 2 * mid);
if (ok) {
l = mid;
} else {
r = mid;
}
}
ans = max(ans, 2 * l);
}
{
int l = 0, r = n / 2 + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (2 * mid + 1 > n) {
r = mid;
continue;
}
ok = false;
fill(used.begin(), used.end(), 0);
build(c, 2 * mid + 1);
if (ok) {
l = mid;
} else {
r = mid;
}
}
ans = max(ans, 2 * l + 1);
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
344 KB |
Output is correct |
| 2 |
Correct |
12 ms |
348 KB |
Output is correct |
| 3 |
Correct |
51 ms |
728 KB |
Output is correct |
| 4 |
Correct |
74 ms |
600 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
12452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5020 ms |
11148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
344 KB |
Output is correct |
| 2 |
Correct |
12 ms |
348 KB |
Output is correct |
| 3 |
Correct |
51 ms |
728 KB |
Output is correct |
| 4 |
Correct |
74 ms |
600 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Execution timed out |
5045 ms |
12452 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
