Submission #1130534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130534		_rain_	Lampice (COCI19_lampice)	C++20	0 / 110	4 ms	2880 KiB

lampice

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

#define N 5000
const int MOD=1e9+7;
const int base=31;
int add(int a,int b){
	return a+b>=MOD?a+b-MOD:a+b;
}
int sub(int a,int b){
	return a-b<0?a-b+MOD:a-b;
}
int mul(int a,int b){
	return (LL)a*b%MOD;
}
int power(int a,int b){
	int res=1;
	for(;b;b>>1,a=mul(a,a)){
		if (b&1) res=mul(res,a);
	}
	return res;
}

vector<int>ke[N+2];
char s[N+2];
int n;
int h[N+2][N+2];

void add_edge(int u,int v){
	ke[u].push_back(v),ke[v].push_back(u);
	return;
}
void Dfs_hash(int root,int u,int p){
	h[root][u]=((LL)h[root][p]*base+s[u]-'a'+1)%MOD;
	for(auto&v:ke[u]){
		if (v==p) continue;
		Dfs_hash(root,v,u);
	}
	return;
}

namespace CENTROID{
	int sub[N+2],vv[N+2],p[N+2],dep[N+2]={},maxh=0,ans=0;
	map<int,bool>mp[N+2];
    map<int,bool>mp2[N+2];
	bool del[N+2];
	void dfs_size(int u,int p){
		sub[u]=1;
		for(auto&v:ke[u]){
			if (v==p||del[v]) continue;
			dfs_size(v,u);
			sub[u]+=sub[v];
		}
		return;
	}
	int find_centroid(int u,int p,int half){
		for(auto&v:ke[u]){
			if (del[v]||v==p) continue;
			if (sub[v]>half) return find_centroid(v,u,half);
		}
		return u;
	}
	void dfs(int u,int p){
		dep[u]=dep[p]+1;
		vv[dep[u]]=u; 
		maxh=max(maxh,dep[u]);
		for(auto&v:ke[u]){
			if (v==p||del[v]) continue;
			dfs(v,u);
		}
	}
	void calc(int root,int u,int p,int t){
		if (t) {
            mp[dep[u]][h[vv[1]][u]]=true;
            // mp2[dep[u]+1][h[root][u]]=true;
        }
		else {
			int addmore=0,pos=0;
            if (mp[dep[u]+1].find(h[root][u])!=mp[dep[u]+1].end()) ans=max(ans,2*(dep[u]+1));
            // if (mp2[dep[u]].find(h[vv[1]][u])!=mp2[dep[u]].end()) ans=max(ans,2*dep[u]);
			if (h[root][u]==h[u][root]){
				pos=dep[u]+1;
				int l=1,r=maxh-dep[u];
				while (l<=r){
					int m=(l+r)>>1;
					if (mp[m].find(h[vv[dep[u]+1]][vv[dep[u]+m]])!=mp[m].end()){
						addmore=2*m;
						l=m+1;
					} else r=m-1;
				}
			}
			// if (root==3) cout<<u<<' '<<maxh<<' '<<pos<<' '<<addmore<<' '<<ans<<'\n';
			ans=max(ans,pos+addmore);
			pos=0,addmore=0;
			if (p==root){
				pos=1;
				int l=0,r=maxh-dep[u];
				while (l<=r){
					int m=(l+r)>>1;
					if (mp[m+1].find(h[vv[dep[u]]][vv[dep[u]+m]])!=mp[m+1].end()){
						addmore=2*(m+1);
						l=m+1;
					} else r=m-1;
				}
			}

			// cout<<u<<' '<<maxh<<'\n';
			ans=max(ans,addmore+pos);
		}
		for(auto&v:ke[u]){
			if (del[v]||v==p) continue;
			calc(root,v,u,t);
		}
	}
	void build(int u){
		dfs_size(u,u);
		u=find_centroid(u,u,sub[u]/2);
		del[u]=true;
		dep[u]=0;
		for(auto&v:ke[u]){
			if (del[v]) continue;
			maxh=0;
			dfs(v,u);
			calc(u,v,u,0);
			calc(u,v,u,1);
		}
		maxh=0;
		dfs(u,u);
		FOR(i,0,maxh) mp[i].clear(),mp2[i].clear();
        reverse(ke[u].begin(),ke[u].end());
        dep[u]=0;
		for(auto&v:ke[u]){
			if (del[v]) continue;
			maxh=0;
			dfs(v,u);
			calc(u,v,u,0);
			calc(u,v,u,1);
		}
		maxh=0;
		dfs(u,u);
		FOR(i,0,maxh) mp[i].clear(),mp2[i].clear();
		for(auto&v:ke[u]) if (!del[v]) build(v);
		return;
	}
}
using namespace CENTROID;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	FOR(i,1,n) cin>>s[i];
	FOR(i,1,n-1){
		int u,v; cin>>u>>v;
		add_edge(u,v);
	}
	FOR(i,1,n) Dfs_hash(i,i,i);
	build(1);
	cout<<ans;
}

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