Submission #977417

#	Time	Username	Problem	Language	Result	Execution time	Memory
977417		boyliguanhan	Lampice (COCI19_lampice)	C++17	110 / 110	1104 ms	18512 KiB

lampice

//The code comes from luogu, and only for time comparison.
#include<bits/stdc++.h>
const int N=55000,mod=998244353;
using ll=long long;
using namespace std;
int n,sz[N],mx[N],d[N],t,qwq[N];
ll B[N],iB[N],h0[N],h1[N]; 
bool vis[N];
vector<int>to[N];
unordered_set<int>bu[N];
char s[N];
ll pw(ll a,int b)
{
	ll res=1;
	for(;b;a=a*a%mod,b>>=1)
		if(b&1)res=res*a%mod;
	return res;
}
int look(int u,int S)
{
	sz[u]=1,vis[u]=1,mx[u]=0;
	int dt=0;
	for(int v:to[u])
		if(!vis[v])
		{
			int g=look(v,S);
			if(mx[g]<mx[dt])dt=g;
			sz[u]+=sz[v],
			mx[u]=max(mx[u],sz[v]);
		}
	mx[u]=max(mx[u],S-sz[u]),
	vis[u]=0;
	if(mx[u]<mx[dt])dt=u;
	return dt;
}
void dfs(int u,int f)
{
	vis[u]=1,d[u]=d[f]+1,qwq[t++]=u,sz[u]=1,
	h1[u]=(h1[f]*26+(s[u]-'a'))%mod,
	h0[u]=((s[u]-'a')*B[d[f]]+h0[f])%mod;
	for(int v:to[u])
		if(!vis[v])dfs(v,u),sz[u]+=sz[v];
	vis[u]=0;
}
bool dfz(int u,int K)
{
	if(K>sz[u])return 0;
	u=look(u,sz[u]),vis[u]=1;
	for(int i=0;i<K;++i)bu[i].clear();
	int e=s[u]-'a';bu[0].insert(e);
	bool ok=0;
	for(int v:to[u])
		if(!vis[v])
		{
			t=0,dfs(v,0);
			for(int i=0;i<t;++i)
			{
				int x=qwq[i];
				if(d[x]==K&&h0[x]==h1[x])ok=1;
				if(d[x]>=K)continue;
				ll W=(h0[x]*iB[d[x]-1]+e*iB[d[x]]+mod-h1[x]*iB[K-1]%mod)%mod;
				if(bu[K-d[x]-1].count(W))ok=1;
			}
			for(int i=0;i<t;++i)
			{
				int x=qwq[i];
				if(d[x]<K)
					bu[d[x]].insert((h0[x]*iB[d[x]-1]+e*iB[d[x]]+mod-h1[x]*iB[K-1]%mod)%mod);
			}
		} 
	for(int v:to[u])
		if(!vis[v]&&dfz(v,K))ok=1;
	vis[u]=0;
	return ok;
}
int main()
{
	scanf("%d%s",&n,s+1),mx[0]=N;
	for(int i=1,u,v;i<n;++i)
		scanf("%d%d",&u,&v),
		to[u].push_back(v),to[v].push_back(u);
	B[0]=iB[0]=1,iB[1]=pw(B[1]=26,mod-2);
	for(int i=2;i<=n;++i)
		B[i]=B[i-1]*B[1]%mod,iB[i]=iB[i-1]*iB[1]%mod;
	int l=0,r=(n+1)>>1;
	while(l+1<r)
	{
		int mid=(l+r)>>1;sz[1]=n;
		if(dfz(1,mid<<1|1))l=mid;
		else r=mid;
	}
	int res=l<<1|1;r=(n>>1)+1;
	while(l+1<r)
	{
		int mid=(l+r)>>1;sz[1]=n;
		if(dfz(1,mid<<1))l=mid;
		else r=mid;
	}
	res=max(res,l<<1);
	printf("%d",res);
	return 0;
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%s",&n,s+1),mx[0]=N;
      |  ~~~~~^~~~~~~~~~~~~~~
lampice.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d",&u,&v),
      |   ~~~~~^~~~~~~~~~~~~~

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