Submission #468591

#	Time	Username	Problem	Language	Result	Execution time	Memory
468591		willi19	Lampice (COCI19_lampice)	C++17	110 / 110	4883 ms	46868 KiB

lampice

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

ll prime = 999983,m1=29,m2=37,m3=47,sz[50100],n,p[50100],cp[50100],cnt;
ll hash_value1[50100][20],hash_value2[50100][20],hash_value3[50100][20],ans,pow_v1[50100],pow_v2[50100],pow_v3[50100],d_ind[50100],max_d[50100];
bool dead[50100],pel[50100][20],hash_table1[1000100],hash_table2[1000100],hash_table3[1000100];
vector<ll> g[50100];
vector<ll> c_comp[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_push1(ll hash_v,ll v)
{
	return (hash_v*m1+v)%prime;
}

ll left_push2(ll hash_v,ll v)
{
	return (hash_v*m2+v)%prime;
}

ll left_push3(ll hash_v,ll v)
{
	return (hash_v*m3+v)%prime;
}

ll right_add1(ll hash_v,ll v,ll ind)
{
	return (hash_v+pow_v1[ind]*v)%prime;
}

ll right_add2(ll hash_v,ll v,ll ind)
{
	return (hash_v+pow_v2[ind]*v)%prime;
}

ll right_add3(ll hash_v,ll v,ll ind)
{
	return (hash_v+pow_v3[ind]*v)%prime;
}

void check_pel(ll start,ll parent,ll d,ll up1,ll up2,ll up3,ll down1,ll down2,ll down3,ll ind,ll root)
{
	up1 = left_push1(up1,(ll)(s[start]-'a'+1));
	up2 = left_push2(up2,(ll)(s[start]-'a'+1));
	up3 = left_push3(up3,(ll)(s[start]-'a'+1));
	down1 = right_add1(down1,(ll)(s[start]-'a'+1),d);
	down2 = right_add2(down2,(ll)(s[start]-'a'+1),d);
	down3 = right_add3(down3,(ll)(s[start]-'a'+1),d);
	hash_value1[start][ind] = up1;
	hash_value2[start][ind] = up2;
	hash_value3[start][ind] = up3;
	c_comp[root].push_back(start);
	max_d[root] = max(max_d[root],d);
	if(up1==down1&&up2==down2&&up3==down3)
		pel[start][ind] = true;
	else
		pel[start][ind] = false;
	for(ll next:g[start])
	{
		if(dead[next] || parent == next)
			continue;
		check_pel(next,start,d+1,up1,up2,up3,down1,down2,down3,ind,root);
	}
}

void update(ll start,ll parent,ll ind)
{
	hash_table1[hash_value1[start][ind]] = true;
	hash_table2[hash_value2[start][ind]] = true;
	hash_table3[hash_value3[start][ind]] = true;
	for(ll next:g[start])
	{
		if(dead[next] || parent == next)
			continue;
		update(next,start,ind);
	}
}

	
void clear_hash(ll root,ll ind)
{
	for(ll next:c_comp[root])
	{
		hash_table1[hash_value1[next][ind]] = false;
		hash_table2[hash_value2[next][ind]] = false;
		hash_table3[hash_value3[next][ind]] = false;
	}
}

void cal_c(ll start,ll parent,ll l,ll d)
{
	p[start] = parent;
	d_ind[d] = start;
	if(d==l)
	{
		cp[start] = start;
		return;
	}
	cp[start] = -1;
	for(ll next:g[start])
	{
		if(dead[next] || parent==next)
			continue;
		cal_c(next,start,l,d+1);
	}
	if(2*d-l>0)
		cp[start] = d_ind[2*d-l];
}

bool dfs_pel(ll start,ll parent,ll l,ll d,ll ind) // 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,ind))
			return true;
	}
	if(2*d-l<=0||!pel[cp[start]][ind])
		return false;
	if(2*d-l-1==0)
		return hash_table1[hash_value1[start][ind]]&&hash_table2[hash_value2[start][ind]]&&hash_table3[hash_value3[start][ind]];
	ll pel_s1 = hash_value1[p[cp[start]]][ind];
	ll pel_s2 = hash_value2[p[cp[start]]][ind];
	ll pel_s3 = hash_value3[p[cp[start]]][ind];
	ll hash_v1 = ((hash_value1[start][ind]-pow_v1[l-d+1]*pel_s1)%prime+prime)%prime;
	ll hash_v2 = ((hash_value2[start][ind]-pow_v2[l-d+1]*pel_s2)%prime+prime)%prime;
	ll hash_v3 = ((hash_value3[start][ind]-pow_v3[l-d+1]*pel_s3)%prime+prime)%prime;
	return hash_table1[hash_v1]&&hash_table2[hash_v2]&&hash_table3[hash_v3];
}

void preprocess(ll start,ll ind)
{
	get_sz(start,-1);
	ll c = get_centroid(start,-1,sz[start]);
	dead[c]=true;
	for(ll next:g[c])
		if(!dead[next])
			preprocess(next,ind+1);
	check_pel(c,-1,0,(ll) 0,(ll) 0,(ll) 0,(ll) 0,(ll) 0,(ll) 0,ind,c);
	dead[c]=false;
	return;
}

bool centroid_decomposition(ll start,ll l,ll ind)
{
	get_sz(start,-1);
	ll c = get_centroid(start,-1,sz[start]);
	if(max_d[c]*2+3<l)
		return false;
	dead[c]=true;
	for(ll next:g[c])
	{
		if(!dead[next]&&centroid_decomposition(next,l,ind+1))
		{
			dead[c] = false;
			return true;
		}
	}
	
	ll root1 = left_push1((ll) 0,(ll)(s[c]-'a'+1));
	ll root2 = left_push2((ll) 0,(ll)(s[c]-'a'+1));
	ll root3 = left_push3((ll) 0,(ll)(s[c]-'a'+1));
	hash_table1[root1] = true;
	hash_table2[root2] = true;
	hash_table3[root3] = true;
	cal_c(c,-1,l,1);
	

	for(ll next:g[c])
	{
		if(dead[next])
			continue;
		if(dfs_pel(next,c,l,2,ind))
		{
			clear_hash(c,ind);
			dead[c] = false;
			return true;
		}
		update(next,c,ind);
	}
	
	
	clear_hash(c,ind);
	hash_table1[root1] = true;
	hash_table2[root2] = true;
	hash_table3[root3] = 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,ind))
		{
			clear_hash(c,ind);
			dead[c] = false;
			return true;
		}
		update(next,c,ind);
	}
	
	clear_hash(c,ind);
	dead[c] = false;
	return false;
}

void init(ll n)
{
	pow_v1[0] = (ll) 1;
	pow_v2[0] = (ll) 1;
	pow_v3[0] = (ll) 1;
	for(ll i=1;i<n;i++)
	{
		pow_v1[i] = pow_v1[i-1]*m1%prime;
		pow_v2[i] = pow_v2[i-1]*m2%prime;
		pow_v3[i] = pow_v3[i-1]*m3%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);
	}
	preprocess(0,0);
	//odd
	ll low = 0;
	ll high = (n-1)/2;
	ll t = 0;
	while(low!=high)
	{
		t++;
		ll mid=(low+high+1)/2;
		if(centroid_decomposition(0,mid*2+1,0))
			low = mid;
		else
			high = mid-1;
		//cout<<low<<" "<<high<<" "<<t<<"\n";
	}
	ans = 2*low+1;
	//even
	low = 0;
	high = (n/2);
	while(low!=high)
	{
		t++;
		ll mid=(low+high+1)/2;
		if(centroid_decomposition(0,mid*2,0))
			low = mid;
		else
			high = mid-1;
		//cout<<low<<" "<<high<<" "<<t<<"\n";
	}
	ans = max(ans,low*2);
	cout<<ans<<"\n";
}

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