oj.uz

Submission #468494

# Submission time Handle Problem Language Result Execution time Memory
468494 2021-08-28T14:59:23 Z willi19 Lampice (COCI19_lampice) C++17
110 / 110
 4765 ms 46748 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 4 ms 3404 KB Output is correct
2 Correct 6 ms 4812 KB Output is correct
3 Correct 21 ms 6708 KB Output is correct
4 Correct 24 ms 7208 KB Output is correct
5 Correct 2 ms 2764 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 1254 ms 41756 KB Output is correct
2 Correct 669 ms 42628 KB Output is correct
3 Correct 503 ms 43460 KB Output is correct
4 Correct 545 ms 45172 KB Output is correct
5 Correct 700 ms 46748 KB Output is correct
6 Correct 336 ms 46732 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4765 ms 43492 KB Output is correct
2 Correct 2989 ms 42116 KB Output is correct
3 Correct 2742 ms 41696 KB Output is correct
4 Correct 2033 ms 43388 KB Output is correct
5 Correct 2850 ms 39156 KB Output is correct
6 Correct 2427 ms 36232 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Correct 6 ms 4812 KB Output is correct
3 Correct 21 ms 6708 KB Output is correct
4 Correct 24 ms 7208 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1254 ms 41756 KB Output is correct
9 Correct 669 ms 42628 KB Output is correct
10 Correct 503 ms 43460 KB Output is correct
11 Correct 545 ms 45172 KB Output is correct
12 Correct 700 ms 46748 KB Output is correct
13 Correct 336 ms 46732 KB Output is correct
14 Correct 4765 ms 43492 KB Output is correct
15 Correct 2989 ms 42116 KB Output is correct
16 Correct 2742 ms 41696 KB Output is correct
17 Correct 2033 ms 43388 KB Output is correct
18 Correct 2850 ms 39156 KB Output is correct
19 Correct 2427 ms 36232 KB Output is correct
20 Correct 1189 ms 37160 KB Output is correct
21 Correct 1045 ms 37312 KB Output is correct
22 Correct 1976 ms 39156 KB Output is correct
23 Correct 667 ms 35588 KB Output is correct
24 Correct 1326 ms 41788 KB Output is correct
25 Correct 2205 ms 42068 KB Output is correct
26 Correct 3568 ms 43960 KB Output is correct
27 Correct 3689 ms 42388 KB Output is correct
28 Correct 842 ms 41788 KB Output is correct
29 Correct 1037 ms 42520 KB Output is correct
30 Correct 1597 ms 43924 KB Output is correct
31 Correct 1992 ms 42176 KB Output is correct
32 Correct 1404 ms 43968 KB Output is correct
33 Correct 514 ms 40256 KB Output is correct