Submission #1065590

#TimeUsernameProblemLanguageResultExecution timeMemory
1065590Flan312Lampice (COCI19_lampice)C++17
110 / 110
2599 ms12196 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define ll long long #define ld long double #define eb emplace_back #define task "" #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout); #define fi first #define se second #define pii pair <int, int> #define tii tuple <int, int, int> #define all(s) s.begin(), s.end() using namespace std; using namespace __gnu_pbds; const ll base = 311; const int nmax = 5e4 + 2; ll pw[nmax]; int n; string a; basic_string <int> adj[nmax]; gp_hash_table <ll, bool> mp; struct Hash { ll hl[nmax], hr[nmax], pw[nmax]; int len; void push_back(char c) { hl[len + 1] = hl[len] * base + c; hr[len + 1] = hr[len] + c * pw[len]; ++len; } void pop_back() { --len; } void clear() { len = 0; } bool isPalin(int l) { return hl[l] == hr[l]; } ll get(int l) { return hl[len] - hl[len - l] * pw[l]; } Hash() { len = 0; pw[0] = 1; for (int i = 1; i < nmax; ++i) pw[i] = pw[i - 1] * base; } } hs; struct centroidDecomposition { int sz[nmax]; bool del[nmax]; void init() { memset(del, 0, (n + 1) * sizeof(bool)); } void dfs(int u, int p) { sz[u] = 1; for (auto &v : adj[u]) { if (v == p || del[v]) continue; dfs(v, u); sz[u] += sz[v]; } } int findCentroid(int u, int p, int total) { for (auto &v : adj[u]) { if (v == p || del[v]) continue; if (sz[v] > (total >> 1)) return findCentroid(v, u, total); } return u; } bool dfs_update(int u, int p, int depth, int len) { hs.push_back(a[u]); if (depth * 2 >= len && hs.isPalin(2 * depth - len)) //duong di qua goc tu 2 dinh con cach goc 1 khoang depth mp[hs.get(len - depth)] = 1; if (depth == len && hs.isPalin(len)) return 1; for (auto &v : adj[u]) { if (v == p || del[v]) continue; if (dfs_update(v, u, depth + 1, len)) return 1; } hs.pop_back(); return 0; } bool dfs_search(int u, int p, int depth, int len) { hs.push_back(a[u]); if (depth * 2 <= len && mp[hs.get(depth)]) //chi 1 nhanh return 1; if (depth == len && hs.isPalin(len)) return 1; for (auto &v : adj[u]) { if (v == p || del[v]) continue; if (dfs_search(v, u, depth + 1, len)) return 1; } hs.pop_back(); return 0; } bool build(int u, int len) { dfs(u, -1); int centroid = findCentroid(u, -1, sz[u]); del[centroid] = 1; for (int turn = 0; turn <= 1; ++turn) { mp.clear(); for (auto &v : adj[centroid]) { if (del[v]) continue; hs.clear(); if (dfs_search(v, centroid, 1, len)) return 1; hs.clear(); hs.push_back(a[centroid]); if (dfs_update(v, centroid, 2, len)) return 1; } reverse(all(adj[centroid])); } for (auto &v : adj[centroid]) { if (del[v]) continue; if (build(v, len)) return 1; } return 0; } } cd; bool check(int mid) { cd.init(); return cd.build(1, mid); } int main() { if (ifstream(task".inp")) nx fast cin >> n >> a; a = ' ' + a; for (int u, v, i = 1; i < n; ++i) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int l = 1, r = (n >> 1), ans = 1; while(l <= r) { int mid = l + r >> 1; if (check(2 * mid)) { ans = max(ans, 2 * mid); l = mid + 1; } else r = mid - 1; } l = 1, r = (n >> 1); while(l <= r) { int mid = l + r >> 1; if (check(2 * mid + 1)) { ans = max(ans, 2 * mid + 1); l = mid + 1; } else r = mid - 1; } cout << ans; }

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:192:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  192 |         int mid = l + r >> 1;
      |                   ~~^~~
lampice.cpp:204:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  204 |         int mid = l + r >> 1;
      |                   ~~^~~
lampice.cpp:8:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:176:31: note: in expansion of macro 'nx'
  176 |     if (ifstream(task".inp")) nx
      |                               ^~
lampice.cpp:8:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:176:31: note: in expansion of macro 'nx'
  176 |     if (ifstream(task".inp")) nx
      |                               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...