Submission #1039171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039171		cnn008	Lampice (COCI19_lampice)	C++17	110 / 110	2132 ms	13620 KiB

lampice

#include "bits/stdc++.h"
using namespace std;
 
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
 
#define int long long
 
const int N=5e4+5;
const int mod=1e9+9;
const int base=47;
 
int n,sz[N],del[N],pw[N],ans=1,k,f;
char c[N];
vector <int> g[N];
map <int,int> mp[N];
void pre_dfs(int u, int p){
	sz[u]=1;
	for(auto v:g[u]) if(v!=p and !del[v]) pre_dfs(v,u),sz[u]+=sz[v];
}
int centroid(int u, int p, int n){
	for(auto v:g[u]) if(v!=p and !del[v] and sz[v]>n/2) return centroid(v,u,n);
	return u;
}
void dfs1(int u, int p, int h, int vr, int vru, int path){
	if(f) return;
	vr=(vr*base+c[u]-'a'+1)%mod;
	vru=(vru+(pw[h-1]*(c[u]-'a'+1)))%mod;
	if(h==k-1){
		if(vr==(vru*base+path)%mod) f=1;
		return;
	}
	int val=(vru*pw[k-h])%mod-vr;
	if(val<0) val+=mod;
	if(mp[k-h-1].count(val)) f=1;
	for(auto v:g[u]) if(v!=p and !del[v]) dfs1(v,u,h+1,vr,vru,path);
}
void dfs2(int u, int p, int h, int vr, int vru){
	if(f) return;
	if(h==k-1) return;
	vr=(vr*base+c[u]-'a'+1)%mod;
	vru=(vru+(pw[h-1]*(c[u]-'a'+1)))%mod;
	int val=(vru*pw[k-h])%mod-vr;
	if(val<0) val+=mod;
	mp[h][val]=1;
	for(auto v:g[u]) if(v!=p and !del[v]) dfs2(v,u,h+1,vr,vru);
}
void dfs3(int u, int p, int h){
	mp[h].clear();
	for(auto v:g[u]) if(v!=p and !del[v]) dfs3(v,u,h+1);
}
void get(int u){
	for(auto v:g[u]){
		if(!del[v]){
			dfs1(v,u,1,c[u]-'a'+1,0,c[u]-'a'+1);
			dfs2(v,u,1,c[u]-'a'+1,0);
		}
	}
	for(auto v:g[u]) if(!del[v]) dfs3(v,u,1);
}
void solve(int u){
	if(f) return;
	pre_dfs(u,0);
	int root=centroid(u,0,sz[u]);
	get(root);
	del[root]=1;
	for(auto v:g[root]) if(!del[v]) solve(v);
}
void sol(){
	cin>>n;
	for(int i=1; i<=n; i++) cin>>c[i];
	for(int i=1; i<n; i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int l=1,r=n/2;
	while(l<=r){
		f=0;
		int mid=(l+r)>>1;
		k=mid+mid;
		for(int i=1; i<=n; i++) del[i]=0;
		solve(1);
		if(f){
			ans=max(ans,k);
			l=mid+1;
		}else r=mid-1;
	}
	l=1,r=n/2;
	while(l<=r){
		f=0;
		int mid=(l+r)>>1;
		k=mid+mid+1;
		for(int i=1; i<=n; i++) del[i]=0;
		solve(1);
		if(f){
			ans=max(ans,k);
			l=mid+1;
		}else r=mid-1;
	}
	cout<<ans;
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    pw[0]=1;
    for(int i=1; i<N; i++) pw[i]=(pw[i-1]*base)%mod;
    int tt=1;
    //cin>>tt; 
    while(tt--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}
/**  /\_/\
*   (= ._.)
*   / >💖 \>💕
**/

Compilation message (stderr)

lampice.cpp:122:9: warning: "/*" within comment [-Wcomment]
  122 | /**  /\_/\
      |

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