Submission #468418

#	Time	Username	Problem	Language	Result	Execution time	Memory
468418		willi19	Lampice (COCI19_lampice)	C++14	17 / 110	5054 ms	11396 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long p1 = 104729,p2=7927,m=29,sz[50100],n,p[50100],cp[50100],ans;
pair<ll,ll> pow_v[50100],up_v[50100];
bool dead[50100],pel[50100];
set<pair<ll,pair<ll,ll> > >tot; //with_root
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;
}

pair<ll,ll> left_push(pair<ll,ll> hash_v,ll v)
{
	return {(hash_v.first*m+v)%p1,(hash_v.second*m+v)%p2};
}

pair<ll,ll> right_add(pair<ll,ll> hash_v,ll v,ll ind)
{
	return {(hash_v.first+pow_v[ind].first*v)%p1,(hash_v.second+pow_v[ind].second*v)%p2};
}

void check_pel(ll start,ll parent,ll d,pair<ll,ll> up,pair<ll,ll> down)
{
	up = left_push(up,(ll)(s[start]-'a'));
	down = right_add(down,(ll)(s[start]-'a'),d);
	up_v[start] = up;
	if(up.first==down.first&&up.second==down.second)
		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,ll d)
{
	pair<ll,ll> up = up_v[start];
	for(ll next:g[start])
	{
		if(dead[next] || parent == next)
			continue;
		update(next,start,d+1);
	}
	pair<ll,pair<ll,ll> > hash_v = {d,up};
	tot.insert(hash_v);
}

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 tot.find({d,{up_v[start]}})!=tot.end();
	pair<ll,ll> pel_s = up_v[p[cp[start]]];
	pair<ll,ll> hash_v = {((up_v[start].first-pow_v[l-d+1].first*pel_s.first)%p1+p1)%p1,((up_v[start].second-pow_v[l-d+1].second*pel_s.second)%p2+p2)%p2};
	return tot.find({l-d+1,hash_v})!=tot.end();
}

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;
		}
	}
	
	tot.clear();
	pair<ll,ll> root = left_push({(ll)0,(ll)0},(ll)(s[c]-'a'));
	tot.insert({1,root});
	check_pel(c,-1,0,{(ll)0,(ll)0},{(ll)0,(ll)0});
	cal_c(c,-1,l,1);
	
	for(ll next:g[c])
	{
		if(dead[next])
			continue;
		if(dfs_pel(next,c,l,2))
		{
			dead[c] = false;
			return true;
		}
		update(next,c,2);
	}
	
	tot.clear();
	tot.insert({1,root});
	
	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;
			return true;
		}
		update(next,c,2);
	}
	
	dead[c] = false;
	return false;
}

void init(ll n)
{
	pow_v[0] = {(ll) 1,(ll) 1};
	for(ll i=1;i<n;i++)
		pow_v[i] = {pow_v[i-1].first*m%p1,pow_v[i-1].second*m%p2};
	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";
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37