| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1098461 |
2024-10-09T12:26:38 Z |
f0rizen |
Lampice (COCI19_lampice) |
C++17 |
|
2737 ms |
12280 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
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;
}
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;
int len;
vector<int> a;
vector<vector<int>> g;
vector<bool> used;
vector<int> sz;
bool ok = false;
vector<int> dep;
vector<vector<int>> dp, rdp;
vector<int> up;
__gnu_pbds::gp_hash_table<int, bool> mp;
void dfs_sz(int v, int p = -1) {
sz[v] = 1;
for (auto u : g[v]) {
if (u != p && !used[u]) {
dep[u] = dep[v] + 1;
dfs_sz(u, v);
sz[v] += sz[u];
}
}
}
void dfs_dp(int v, int p = -1) {
dp[0][v] = (mul(dp[0][p], P) + a[v]) % mod;
rdp[0][v] = (mul(a[v], pw[dep[v] - 1]) + rdp[0][p]) % mod;
dp[1][v] = (mul(dp[1][p], P) + a[v]) % mod;
rdp[1][v] = (mul(a[v], pw[dep[v]]) + rdp[1][p]) % mod;
for (auto u : g[v]) {
if (u != p && !used[u]) {
dfs_dp(u, v);
}
}
}
void dfs_ans(int v, int p = -1) {
up.push_back(v);
int k = len - dep[v] - 1;
if (k > 0) {
if (len - 2 * k > 0) {
int u = up[(int) up.size() - (k + 1)];
if (dp[1][u] == rdp[1][u]) {
int h = sub(dp[1][v], mul(pw[k], dp[1][u]));
if (mp.find(h) != mp.end()) {
ok = true;
}
}
} else if (len - 2 * k == 0) {
int h = dp[1][v];
if (mp.find(h) != mp.end()) {
ok = true;
}
}
} else if (k == 0) {
if (dp[1][v] == rdp[1][v]) {
ok = true;
}
}
for (auto u : g[v]) {
if (u != p && !used[u]) {
dfs_ans(u, v);
}
}
up.pop_back();
}
void dfs_insert(int v, int p = -1) {
mp[dp[0][v]] = 1;
for (auto u : g[v]) {
if (u != p && !used[u]) {
dfs_insert(u, v);
}
}
}
void dfs_clear(int v, int p = -1) {
dep[v] = 0;
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);
}
}
}
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;
}
void build(int v) {
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);
}
}
up.push_back(v);
for (auto u : g[v]) {
if (!used[u]) {
dfs_ans(u, v);
dfs_insert(u, v);
}
}
up.pop_back();
mp.clear();
up.push_back(v);
for (int i = (int) g[v].size() - 1; i >= 0; --i) {
int u = g[v][i];
if (!used[u]) {
dfs_ans(u, v);
dfs_insert(u, v);
}
}
up.pop_back();
mp.clear();
dfs_clear(v);
used[v] = 1;
for (auto u : g[v]) {
if (!used[u]) {
build(centroid(u, v, sz[u]));
}
}
}
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);
}
used.resize(n);
sz.resize(n);
dep.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;
}
len = 2 * mid;
ok = false;
fill(used.begin(), used.end(), 0);
build(c);
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;
}
len = 2 * mid + 1;
ok = false;
fill(used.begin(), used.end(), 0);
build(c);
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 |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
10 ms |
348 KB |
Output is correct |
| 3 |
Correct |
41 ms |
604 KB |
Output is correct |
| 4 |
Correct |
60 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 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 |
Correct |
2671 ms |
10144 KB |
Output is correct |
| 2 |
Correct |
2524 ms |
10320 KB |
Output is correct |
| 3 |
Incorrect |
2737 ms |
10476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
12280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
10 ms |
348 KB |
Output is correct |
| 3 |
Correct |
41 ms |
604 KB |
Output is correct |
| 4 |
Correct |
60 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2671 ms |
10144 KB |
Output is correct |
| 9 |
Correct |
2524 ms |
10320 KB |
Output is correct |
| 10 |
Incorrect |
2737 ms |
10476 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
