oj.uz

Submission #1049135

# Submission time Handle Problem Language Result Execution time Memory
1049135 2024-08-08T13:51:22 Z hahahaha Lampice (COCI19_lampice) C++17
110 / 110
 863 ms 18244 KB 
#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]*B[K-d[x]]+e*B[K-d[x]-1]+mod-h1[x]%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]*B[K-d[x]]+e*B[K-d[x]-1]+mod-h1[x]%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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d%s",&n,s+1),mx[0]=N;
      |  ~~~~~^~~~~~~~~~~~~~~
lampice.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d",&u,&v),
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4836 KB Output is correct
2 Correct 3 ms 4876 KB Output is correct
3 Correct 8 ms 4956 KB Output is correct
4 Correct 7 ms 4952 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 16496 KB Output is correct
2 Correct 177 ms 16728 KB Output is correct
3 Correct 132 ms 16988 KB Output is correct
4 Correct 178 ms 17492 KB Output is correct
5 Correct 188 ms 18244 KB Output is correct
6 Correct 50 ms 17500 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 13124 KB Output is correct
2 Correct 553 ms 12368 KB Output is correct
3 Correct 531 ms 12636 KB Output is correct
4 Correct 360 ms 12456 KB Output is correct
5 Correct 349 ms 11600 KB Output is correct
6 Correct 427 ms 11968 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4836 KB Output is correct
2 Correct 3 ms 4876 KB Output is correct
3 Correct 8 ms 4956 KB Output is correct
4 Correct 7 ms 4952 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 275 ms 16496 KB Output is correct
9 Correct 177 ms 16728 KB Output is correct
10 Correct 132 ms 16988 KB Output is correct
11 Correct 178 ms 17492 KB Output is correct
12 Correct 188 ms 18244 KB Output is correct
13 Correct 50 ms 17500 KB Output is correct
14 Correct 791 ms 13124 KB Output is correct
15 Correct 553 ms 12368 KB Output is correct
16 Correct 531 ms 12636 KB Output is correct
17 Correct 360 ms 12456 KB Output is correct
18 Correct 349 ms 11600 KB Output is correct
19 Correct 427 ms 11968 KB Output is correct
20 Correct 502 ms 10072 KB Output is correct
21 Correct 634 ms 10836 KB Output is correct
22 Correct 708 ms 11368 KB Output is correct
23 Correct 215 ms 9600 KB Output is correct
24 Correct 405 ms 11348 KB Output is correct
25 Correct 396 ms 10960 KB Output is correct
26 Correct 620 ms 12892 KB Output is correct
27 Correct 863 ms 11608 KB Output is correct
28 Correct 483 ms 9560 KB Output is correct
29 Correct 518 ms 9820 KB Output is correct
30 Correct 302 ms 12632 KB Output is correct
31 Correct 571 ms 10588 KB Output is correct
32 Correct 169 ms 13908 KB Output is correct
33 Correct 351 ms 11192 KB Output is correct