Submission #1021473

#TimeUsernameProblemLanguageResultExecution timeMemory
1021473LOLOLOLampice (COCI19_lampice)C++14
110 / 110
2001 ms14168 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 50000 + 10; ll mod = 1e9 + 7; ll pw[N]; ll base = 256; map <ll, bool> mp[N]; ll a[N]; int n; bool vis[N]; int sz[N]; vector <int> ed[N]; void dfs(int u, int v) { sz[u] = 1; for (auto x : ed[u]) { if (x == v || vis[x]) continue; dfs(x, u); sz[u] += sz[x]; } } int find_centroid(int u, int v, int ss) { for (auto x : ed[u]) { if (x == v || vis[x]) continue; if (sz[x] * 2 > ss) return find_centroid(x, u, ss); } return u; } int mx = 0, len = 0, root = 0; void run(int u, int v, int upd, int h, ll up, ll down, int &is) { mx = max(mx, h); up = (up * base + a[u]) % mod; down = (down + pw[h - 1] * a[u]) % mod; ll val = (down * pw[len - h] - up + mod) % mod; if (upd) { mp[h][val] = 1; } else { if (h + 1 == len && (down * base + root) % mod == up) { is = 1; return; } if (len > h && mp[len - h - 1].find(val) != mp[len - h - 1].end()) { is = 1; return; } } if (h < len) { for (auto x : ed[u]) { if (x == v || vis[x]) continue; run(x, u, upd, h + 1, up, down, is); mx = max(mx, h + 1); if (is) return; } } } void process(int u, int &is) { dfs(u, 0); int cen = find_centroid(u, 0, sz[u]); vis[cen] = 1; root = a[cen]; mx = 0; for (auto x : ed[cen]) { if (vis[x]) continue; run(x, 0, 0, 1, root, 0, is); if (is) return; run(x, 0, 1, 1, root, 0, is); } for (int i = 0; i <= mx; i++) mp[i].clear(); for (auto x : ed[cen]) { if (vis[x]) continue; process(x, is); if (is) return; } } bool check(int x) { for (int i = 0; i <= n; i++) mp[i].clear(); mem(vis, 0); int is = 0; len = x; process(1, is); return is; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; string str; cin >> str; str = '0' + str; for (int i = 1; i <= n; i++) a[i] = (str[i] - 'a' + 1); pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = (pw[i - 1] * base) % mod; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; ed[a].pb(b); ed[b].pb(a); } int ans = 1; for (int i = 0; i < 2; i++) { int l = 0, r = n / 2 + 1; while (r - l > 1) { int m = (l + r) / 2; if (check(m * 2 + i)) { ans = max(ans, m * 2 + i); l = m; } else { r = m; } } } cout << ans << '\n'; 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...