oj.uz

Submission #977417

# Submission time Handle Problem Language Result Execution time Memory
977417 2024-05-07T22:52:37 Z boyliguanhan Lampice (COCI19_lampice) C++17
110 / 110
 1104 ms 18512 KB 
//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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 4 ms 7000 KB Output is correct
3 Correct 11 ms 6892 KB Output is correct
4 Correct 10 ms 6748 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 16728 KB Output is correct
2 Correct 207 ms 17204 KB Output is correct
3 Correct 182 ms 17476 KB Output is correct
4 Correct 205 ms 18000 KB Output is correct
5 Correct 247 ms 18512 KB Output is correct
6 Correct 87 ms 17756 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 12888 KB Output is correct
2 Correct 573 ms 12592 KB Output is correct
3 Correct 598 ms 13176 KB Output is correct
4 Correct 343 ms 12716 KB Output is correct
5 Correct 435 ms 12268 KB Output is correct
6 Correct 520 ms 11876 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 4 ms 7000 KB Output is correct
3 Correct 11 ms 6892 KB Output is correct
4 Correct 10 ms 6748 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 360 ms 16728 KB Output is correct
9 Correct 207 ms 17204 KB Output is correct
10 Correct 182 ms 17476 KB Output is correct
11 Correct 205 ms 18000 KB Output is correct
12 Correct 247 ms 18512 KB Output is correct
13 Correct 87 ms 17756 KB Output is correct
14 Correct 922 ms 12888 KB Output is correct
15 Correct 573 ms 12592 KB Output is correct
16 Correct 598 ms 13176 KB Output is correct
17 Correct 343 ms 12716 KB Output is correct
18 Correct 435 ms 12268 KB Output is correct
19 Correct 520 ms 11876 KB Output is correct
20 Correct 620 ms 10228 KB Output is correct
21 Correct 789 ms 10992 KB Output is correct
22 Correct 865 ms 11380 KB Output is correct
23 Correct 320 ms 9592 KB Output is correct
24 Correct 484 ms 11436 KB Output is correct
25 Correct 484 ms 11096 KB Output is correct
26 Correct 742 ms 13016 KB Output is correct
27 Correct 1104 ms 11884 KB Output is correct
28 Correct 613 ms 9788 KB Output is correct
29 Correct 623 ms 9816 KB Output is correct
30 Correct 373 ms 12636 KB Output is correct
31 Correct 721 ms 10652 KB Output is correct
32 Correct 262 ms 13792 KB Output is correct
33 Correct 442 ms 11192 KB Output is correct