Submission #486774

#TimeUsernameProblemLanguageResultExecution timeMemory
486774jalsolLampice (COCI19_lampice)C++17
17 / 110
5085 ms12224 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; // ============================================================================= namespace KACTL { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wshadow" #define rep(i, a, b) for(int i = a; i < (b); ++i) #define sz(x) (int)(x).size() #define pii pair<int, int> #define vi vector<int> // content goes here struct H { typedef uint64_t ull; ull x; H(ull x=0) : x(x) {} #define OP(O,A,B) H operator O(H o) { ull r = x; asm \ (A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; } OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx") H operator-(H o) { return *this + ~o.x; } ull get() const { return x + !~x; } bool operator==(H o) const { return get() == o.get(); } bool operator<(H o) const { return get() < o.get(); } }; static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok) struct HashInterval { vector<H> ha, pw; HashInterval(string& str) : ha(sz(str)+1), pw(ha) { pw[0] = 1; rep(i,0,sz(str)) ha[i+1] = ha[i] * C + str[i], pw[i+1] = pw[i] * C; } H hashInterval(int a, int b) { // hash [a, b) return ha[b] - ha[a] * pw[b - a]; } }; vector<H> getHashes(string& str, int length) { if (sz(str) < length) return {}; H h = 0, pw = 1; rep(i,0,length) h = h * C + str[i], pw = pw * C; vector<H> ret = {h}; rep(i,length,sz(str)) { ret.push_back(h = h * C + str[i] - pw * str[i-length]); } return ret; } H hashString(string& s){H h{}; for(char c:s) h=h*C+c;return h;} // content ends here #undef rep #undef sz #undef pii #undef vi #pragma GCC diagnostic pop } // namespace KACTL using namespace KACTL; constexpr int maxn = 5e4 + 5; constexpr int logn = 20; constexpr int base = 31; int n; char a[maxn]; vector<int> g[maxn]; H power[maxn]; H hdown[maxn], hup[maxn]; bool found; bool rem[maxn]; int sz[maxn]; int up[maxn][logn]; int dep[maxn]; vector<int> node; vector<pair<H, 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]; } H 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].x != hup[C].x) continue; H 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.x != ohash.x) 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...