Submission #1084864

#TimeUsernameProblemLanguageResultExecution timeMemory
1084864nmtsLampice (COCI19_lampice)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl '\n' #define ll long long const int maxn = 5e4 + 6; using namespace std; using namespace __gnu_pbds; const int base = 311; int n; basic_string<int> edges[maxn]; int ans = 1; char a[maxn]; gp_hash_table<ll, bool> m; struct Hash { ll pw[maxn], hash_val[maxn], pre_hash[maxn]; int n; void prepare(int sz) { n = 0; pw[0] = 1; for (int i = 1; i <= sz; ++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() { memset(del, 0, sizeof(del)); // nhanh hơn vòng for } void dfs(int u, int p) { sz[u] = 1; for (int v : edges[u]) if (v != p && !del[v]) { dfs(v, u); sz[u] += sz[v]; } } int find_centroid(int u, int p, int total_size) { for (int v : edges[u]) if (v != p && !del[v] && sz[v] > total_size / 2) return find_centroid(v, u, total_size); 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 true; if (height == len && hs.IsPalin(len)) return true; for (int v : edges[u]) if (v != p && !del[v]) if (get(v, u, height + 1, len)) return true; hs.pop(); return false; } 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 true; for (int v : edges[u]) if (v != p && !del[v]) if (update(v, u, height + 1, len)) return true; hs.pop(); return false; } bool decompose(int u, int len) { dfs(u, 0); int total_size = sz[u]; int c = find_centroid(u, 0, total_size); 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 true; hs.clear(); hs.push(a[c]); if (update(v, c, 2, len)) return true; } } reverse(edges[c].begin(), edges[c].end()); // để đảm bảo không bỏ sót cạnh nào } for (int v : edges[c]) if (!del[v]) if (decompose(v, len)) return true; return false; } } 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)) maximize(ans, 2 * mid + ok), l = mid + 1; else r = mid - 1; } } void solve() { cin >> n; hs.prepare(n + 1); 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); tknp(1, n >> 1, 1); cout << ans << endl; } int32_t main() { faster; solve(); return 0; }

Compilation message (stderr)

lampice.cpp: In function 'void tknp(int, int, int)':
lampice.cpp:139:13: error: 'maximize' was not declared in this scope
  139 |             maximize(ans, 2 * mid + ok), l = mid + 1;
      |             ^~~~~~~~