Submission #468420

#TimeUsernameProblemLanguageResultExecution timeMemory
468420willi19Lampice (COCI19_lampice)C++14
17 / 110
5038 ms7496 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; long long prime = 99991,m=29,sz[50100],n,p[50100],cp[50100],hash_value[50100],ans,pow_v[50100]; bool dead[50100],pel[50100],hash_table[100100]; vector<ll> g[50100]; string s; // -> t*m+v // <- t+v*pow() void get_sz(ll start,ll parent) { sz[start] = 1; for(ll next:g[start]) { if(dead[next] ||parent == next) continue; get_sz(next,start); sz[start] += sz[next]; } } ll get_centroid(ll start,ll parent,ll tree_sz) { for(ll next:g[start]) { if(dead[next]||next==parent) continue; if(sz[next]>tree_sz/2) return get_centroid(next,start,tree_sz); } return start; } ll left_push(ll hash_v,ll v) { return (hash_v*m+v)%prime; } ll right_add(ll hash_v,ll v,ll ind) { return (hash_v+pow_v[ind]*v)%prime; } void check_pel(ll start,ll parent,ll d,ll up,ll down) { up = left_push(up,(ll)(s[start]-'a'+1)); down = right_add(down,(ll)(s[start]-'a'+1),d); hash_value[start] = up; if(up==down) pel[start] = true; else pel[start] = false; for(ll next:g[start]) { if(dead[next] || parent == next) continue; check_pel(next,start,d+1,up,down); } } void update(ll start,ll parent) { hash_table[hash_value[start]] = true; for(ll next:g[start]) { if(dead[next] || parent == next) continue; update(next,start); } } void clear_hash(ll start,ll parent) { hash_table[hash_value[start]] = false; for(ll next:g[start]) { if(dead[next] || parent == next) continue; clear_hash(next,start); } } void cal_c(ll start,ll parent,ll l,ll d) { p[start] = parent; if(d==l) { cp[start] = start; return; } if(g[start].size()==1&&2*d-l>0) { cp[start] = start; for(ll i=0;i<l-d;i++) cp[start] = p[cp[start]]; return; } for(ll next:g[start]) { if(dead[next] || parent==next) continue; cal_c(next,start,l,d+1); cp[start] = cp[next]; } if(2*d-l>0) cp[start] = p[p[cp[start]]]; } bool dfs_pel(ll start,ll parent,ll l,ll d) // l is length of pel, d is depth, l-d for other sub tree, 2d-l+1>=0, up is better for calculate { if(d>l) return false; for(ll next:g[start]) { if(next==parent||dead[next]) continue; if(dfs_pel(next,start,l,d+1)) return true; } if(2*d-l<=0||!pel[cp[start]]) return false; if(2*d-l-1==0) return hash_table[hash_value[start]]; ll pel_s = hash_value[p[cp[start]]]; ll hash_v = ((hash_value[start]-pow_v[l-d+1]*pel_s)%prime+prime)%prime; return hash_table[hash_v]; } bool centroid_decomposition(ll start,ll l) { get_sz(start,-1); ll c = get_centroid(start,-1,sz[start]); dead[c]=true; for(ll next:g[c]) { if(!dead[next]&&centroid_decomposition(next,l)) { dead[c] = false; return true; } } ll root = left_push((ll) 0,(ll)(s[c]-'a'+1)); hash_table[root] = true; check_pel(c,-1,0,(ll) 0,(ll) 0); cal_c(c,-1,l,1); /*cout<<c<<" "<<l<<"\n"; for(int i=0;i<n;i++) cout<<hash_value[i]<<" "; cout<<"\n"; for(int i=0;i<n;i++) cout<<cp[i]<<" "; cout<<"\n"; for(int i=0;i<n;i++) cout<<pel[i]<<" "; cout<<"\n";*/ for(ll next:g[c]) { if(dead[next]) continue; if(dfs_pel(next,c,l,2)) { dead[c] = false; clear_hash(c,-1); return true; } update(next,c); } clear_hash(c,-1); hash_table[root] = true; for(ll i = g[c].size()-1;i>=0;i--) { ll next = g[c][i]; if(dead[next]) continue; if(dfs_pel(next,c,l,2)) { dead[c] = false; clear_hash(c,-1); return true; } update(next,c); } clear_hash(c,-1); dead[c] = false; return false; } void init(ll n) { pow_v[0] = (ll) 1; for(ll i=1;i<n;i++) pow_v[i] = pow_v[i-1]*m%prime; return; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin>>n; cin>>s; init(n); for(int i=0;i<n-1;i++) { ll a,b; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } //odd ll low = 0; ll high = (n-1)/2; while(low!=high) { ll mid=(low+high+1)/2; if(centroid_decomposition(0,mid*2+1)) low = mid; else high = mid-1; } ans = 2*low+1; //even low = 0; high = (n/2); while(low!=high) { ll mid=(low+high+1)/2; if(centroid_decomposition(0,mid*2)) low = mid; else high = mid-1; } ans = max(ans,low*2); 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...