제출 #1084843

#제출 시각아이디문제언어결과실행 시간메모리
1084843nmtsLampice (COCI19_lampice)C++17
0 / 110
5050 ms9816 KiB
#include <bits/stdc++.h> #define file(name) freopen(name".inp" , "r" , stdin);freopen(name".out" , "w" , stdout); #define faster ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pii pair<int, int> #define fi first #define se second #define mii map<int, int> #define reset(a,val) memset(a ,val , sizeof(a)) #define endl '\n' #define ll long long const int maxn = 5e4 + 6; const int mod= 1e9 + 7; const ll INFLL= 3e18 + 5; const int INF = 1e9 + 5 ; const int LOG = 20; using namespace std; const int base = 311; int n; vector<int> edges[maxn]; int ans = 1; char a[maxn]; map<ll , bool> m; struct Hash { ll pw[maxn], hash_val[maxn], pre_hash[maxn]; int n; void prepare() { n = 0; pw[0] = 1; for (int i = 1; i <= 50000; ++i) pw[i] = pw[i - 1] * base; } void push(char c) { n++; hash_val[n] = hash_val[n - 1] * base + c; pre_hash[n] = pre_hash[n - 1] + c * pw[n - 1]; } void pop() { n--; } void clear() { n = 0; } bool IsPalin(int l) { return hash_val[l] == pre_hash[l]; } ll get(int l) { return hash_val[n] - hash_val[n - l] * pw[l]; } } hs; struct CD { int sz[maxn]; bool del[maxn]; void init() { for (int i = 1; i <= n; ++i) del[i] = 0; } void dfs(int u, int p) { sz[u] = 1; for (int v : edges[u]) if (v != p && del[v] == 0) { dfs(v, u); sz[u] += sz[v]; } } int find_centroid(int u, int p) { for (int v : edges[u]) if (v != p && !del[v]) if (sz[v] > sz[u] / 2) return find_centroid(v, u); return u; } bool get(int u, int p, int height, int len) { hs.push(a[u]); if (2 * height <= len && m[hs.get(height)]) return 1; if (height == len && hs.IsPalin(len)) return 1; for (int v : edges[u]) if (v != p && !del[v]) if (get(v, u, height + 1, len)) return 1; hs.pop(); return 0; } bool update(int u, int p, int height, int len) { hs.push(a[u]); if (height * 2 >= len && hs.IsPalin(height * 2 - len)) m[hs.get(len - height)] = 1; if (height == len && hs.IsPalin(len)) return 1; for (int v : edges[u]) if (v != p && !del[v]) if (update(v, u, height + 1, len)) return 1; hs.pop(); return 0; } bool decompose(int u, int len) { dfs(u, 0); int c = find_centroid(u, 0); del[c] = 1; for (int turn = 1; turn <= 2; ++turn) { m.clear(); for (int v : edges[c]) if (!del[v]) { hs.clear(); if (get(v, c, 1, len)) return 1; hs.clear(); hs.push(a[c]); if (update(v, c, 2, len)) return 1; } reverse(edges[c].begin(), edges[c].end()); } for (int v : edges[c]) if (!del[v]) if (decompose(v, len)) return 1; return 0; } } cd; void tknp(int l, int r, int ok) { while (l <= r) { int mid = (l + r) >> 1; cd.init(); if (cd.decompose(1, 2 * mid + ok)) ans = 2 * mid + ok, l = mid + 1; else r = mid - 1; } } void solve() { hs.prepare(); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; edges[u].push_back(v); edges[v].push_back(u); } tknp(1, n >> 1, 0); // tìm chuỗi palindrome có độ dài chẵn tknp(1, n >> 1, 1); // tìm chuỗi palindrome có độ dài lẻ cout << ans << endl; } int32_t main() { faster; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...