oj.uz

Submission #468591

# Submission time Handle Problem Language Result Execution time Memory
468591 2021-08-28T23:18:54 Z willi19 Lampice (COCI19_lampice) C++17
110 / 110
 4883 ms 46868 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3532 KB Output is correct
2 Correct 5 ms 4812 KB Output is correct
3 Correct 21 ms 6744 KB Output is correct
4 Correct 20 ms 7220 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 41936 KB Output is correct
2 Correct 613 ms 42700 KB Output is correct
3 Correct 468 ms 43480 KB Output is correct
4 Correct 532 ms 45152 KB Output is correct
5 Correct 618 ms 46868 KB Output is correct
6 Correct 298 ms 46864 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4883 ms 43632 KB Output is correct
2 Correct 2950 ms 42784 KB Output is correct
3 Correct 2857 ms 42428 KB Output is correct
4 Correct 1986 ms 44116 KB Output is correct
5 Correct 2787 ms 38724 KB Output is correct
6 Correct 2602 ms 35848 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3532 KB Output is correct
2 Correct 5 ms 4812 KB Output is correct
3 Correct 21 ms 6744 KB Output is correct
4 Correct 20 ms 7220 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1195 ms 41936 KB Output is correct
9 Correct 613 ms 42700 KB Output is correct
10 Correct 468 ms 43480 KB Output is correct
11 Correct 532 ms 45152 KB Output is correct
12 Correct 618 ms 46868 KB Output is correct
13 Correct 298 ms 46864 KB Output is correct
14 Correct 4883 ms 43632 KB Output is correct
15 Correct 2950 ms 42784 KB Output is correct
16 Correct 2857 ms 42428 KB Output is correct
17 Correct 1986 ms 44116 KB Output is correct
18 Correct 2787 ms 38724 KB Output is correct
19 Correct 2602 ms 35848 KB Output is correct
20 Correct 1083 ms 36640 KB Output is correct
21 Correct 1026 ms 36724 KB Output is correct
22 Correct 1869 ms 38588 KB Output is correct
23 Correct 635 ms 35132 KB Output is correct
24 Correct 1306 ms 41272 KB Output is correct
25 Correct 2205 ms 41596 KB Output is correct
26 Correct 3587 ms 43404 KB Output is correct
27 Correct 3805 ms 42064 KB Output is correct
28 Correct 854 ms 41104 KB Output is correct
29 Correct 1049 ms 41980 KB Output is correct
30 Correct 1556 ms 43468 KB Output is correct
31 Correct 2000 ms 41528 KB Output is correct
32 Correct 1372 ms 43452 KB Output is correct
33 Correct 496 ms 39740 KB Output is correct