Submission #486765

#TimeUsernameProblemLanguageResultExecution timeMemory
486765jalsolLampice (COCI19_lampice)C++17
17 / 110
5091 ms11848 KiB
#ifdef LOCAL #include "local.h" #else #include <bits/stdc++.h> #define debug(...) #define DB(...) #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif using namespace std; static const bool __initialization = []() { cin.tie(nullptr)->sync_with_stdio(false); #define TASK "empty" if (fopen(TASK".inp", "r")) { (void)(!freopen(TASK".inp", "r", stdin)); (void)(!freopen(TASK".out", "w", stdout)); } return true; }(); using ll = long long; using ld = long double; #define fi first #define se second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define For(i, l, r) for (int i = (l); i <= (r); ++i) #define Ford(i, r, l) for (int i = (r); i >= (l); --i) #define Rep(i, n) For (i, 0, (n) - 1) #define Repd(i, n) Ford (i, (n) - 1, 0) #define Fe(...) for (auto __VA_ARGS__) template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); } template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; } template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; } constexpr ld eps = 1e-9; constexpr int inf = 1e9; constexpr ll linf = 1e18; // ============================================================================= constexpr int maxn = 5e4 + 5; constexpr int logn = 20; constexpr int base = 31; struct mint { int v; static constexpr int mod = 1e9 + 7; mint() : v(0) {} mint(ll _v) : v(int(_v % mod)) { v += (v < 0) * mod; } mint& operator+=(const mint& o) { if ((v += o.v) >= mod) v -= mod; return *this; } mint& operator-=(const mint& o) { if ((v -= o.v) < 0) v += mod; return *this; } mint& operator*=(const mint& o) { return *this = mint(1LL * v * o.v); } friend mint operator+(const mint& a, const mint& b) { return mint(a) += b; } friend mint operator-(const mint& a, const mint& b) { return mint(a) -= b; } friend mint operator*(const mint& a, const mint& b) { return mint(a) *= b; } friend bool operator==(const mint& a, const mint& b) { return a.v == b.v; } friend bool operator!=(const mint& a, const mint& b) { return a.v != b.v; } bool operator<(const mint& o) const { return v < o.v; } }; int n; char a[maxn]; vector<int> g[maxn]; mint power[maxn]; mint hdown[maxn], hup[maxn]; bool found; bool rem[maxn]; int sz[maxn]; int up[maxn][logn]; int dep[maxn]; vector<int> node; vector<pair<mint, int>> layer[maxn]; void getSz(int u, int p) { sz[u] = 1; Fe (v : g[u]) { if (rem[v] || v == p) continue; getSz(v, u); sz[u] += sz[v]; } } int getCen(int target, int u, int p) { Fe (v : g[u]) { if (rem[v] || v == p) continue; if (sz[v] * 2 > target) return getCen(target, v, u); } return u; } void prepare(int u, int p) { node.push_back(u); layer[dep[u]].emplace_back(hdown[u], u); For (i, 1, logn - 1) { up[u][i] = up[up[u][i - 1]][i - 1]; } Fe (v : g[u]) { if (rem[v] || v == p) continue; up[v][0] = u; dep[v] = dep[u] + 1; hdown[v] = hdown[u] * base + (a[v] - 'a' + 1); hup[v] = hup[u] + power[dep[v] - 1] * (a[v] - 'a' + 1); prepare(v, u); } } int lift(int u, int dist) { Repd (i, logn) { if (dist >> i & 1) u = up[u][i]; } return u; } int getLca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int dist = dep[u] - dep[v]; u = lift(u, dist); if (u == v) return u; Repd (i, logn) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } mint getHash(int u, int v) { return hdown[u] - hdown[up[v][0]] * power[dep[u] - dep[v] + 1]; } void calc(int u, int len) { if (found) return; hdown[u] = a[u] - 'a' + 1; hup[u] = a[u] - 'a' + 1; node.clear(); up[u][0] = 0; dep[u] = 1; prepare(u, -1); For (i, 1, n) { sort(all(layer[i])); } Fe (A : node) { if (found) break; int odist = len - dep[A] + 1; if (odist > dep[A] || odist < 1) continue; const auto& cur = layer[odist]; int C = lift(A, odist - 1); if (hdown[C] != hup[C]) continue; mint ohash = getHash(A, C); auto it = lower_bound(all(cur), pair(ohash, -1)); if (it == cur.end()) { continue; } while (it != cur.end()) { if (it->fi != ohash) break; int B = it->se; if (getLca(A, B) == u) { found = true; break; } else { ++it; } } } For (i, 1, n) { layer[i].clear(); } } void cd(int u, int len) { if (found) return; getSz(u, -1); u = getCen(sz[u], u, -1); rem[u] = true; calc(u, len); for (int v : g[u]) { if (rem[v] == false) { cd(v, len); } } } bool check(int len) { found = false; memset(rem, false, sizeof(rem)); cd(1, len); return found; } signed main() { cin >> n >> (a + 1); Rep (_, n - 1) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } power[0] = 1; For (i, 1, n) power[i] = power[i - 1] * base; int l, r; int ans = 0; l = 0, r = n / 2; while (l <= r) { int m = (l + r) / 2; if (check(2 * m + 1)) { l = m + 1; } else { r = m - 1; } } chmax(ans, 2 * r + 1); l = 1, r = n / 2; while (l <= r) { int m = (l + r) / 2; if (check(2 * m)) { l = m + 1; } else { r = m - 1; } } chmax(ans, 2 * r); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...