Submission #1130696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130696		_rain_	Lampice (COCI19_lampice)	C++20	0 / 110	4 ms	3908 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 50000
const int MOD=998244353;
const int base=31;

vector<int>ke[N+2];
char s[N+2];
int power[N+2],h[N+2],up[N+2],val[N+2];
int n;

void add_edge(int u,int v){
	ke[u].push_back(v),ke[v].push_back(u);
	return;
}
	int sub[N+2],dep[N+2],maxh=0;
	map<int,bool> cnt[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;
	}
	bool calc(int root,int u,int p,int len){
		dep[u]=dep[p]+1;
		maxh=max(maxh,dep[u]);
		if (dep[u]>len) return false;
		h[dep[u]]=((LL)h[dep[u]-1]*base+val[u])%MOD;
		up[dep[u]]=((LL)val[u]*power[dep[u]-1]+up[dep[u]-1])%MOD;
		int need=((LL)up[dep[u]]*power[len-dep[u]]-h[dep[u]]+MOD)%MOD;
		if (h[dep[u]]==up[dep[u]]&&dep[u]==len) {
			return true;
		}
		if (cnt[len-dep[u]].find(need)!=cnt[len-dep[u]].end()) {
			return true;
		}
		for(auto&v:ke[u]){
			if (del[v]||v==p) continue;
			if (calc(root,v,u,len)) return true;
		}
		return false;
	}
	void add(int u,int p,int len){
		dep[u]=dep[p]+1;
		maxh=max(maxh,dep[u]);
		if (dep[u]>len) return;
		h[dep[u]]=((LL)h[dep[u]-1]*base+val[u])%MOD;
		up[dep[u]]=((LL)val[u]*power[dep[u]-1]+up[dep[u]-1])%MOD;
		int need=((LL)up[dep[u]]*power[len-dep[u]]-h[dep[u]]+MOD)%MOD;
		cnt[dep[u]][need]=true;
		for(auto&v:ke[u]){
			if (del[v]||v==p) continue;
			add(v,u,len);
		}
	}
	
	bool build(int u,int len){
		dfs_size(u,u);
		u=find_centroid(u,u,sub[u]/2);
		del[u]=true;
		maxh=0;
		for(auto&v:ke[u]){
			if (del[v]) continue;
			h[1]=up[1]=val[u]; dep[u]=1;
			if (calc(u,v,u,len)) return true;
			dep[u]=0; h[0]=up[0]=0;
			add(v,u,len);
		}
		FOR(i,0,maxh) cnt[i].clear();
		for(auto&v:ke[u]) {
			if (!del[v]) if (build(v,len)) return true;
		}
		return false;
	}

bool check(int len){
	if (len>n) return false;
	if (len<=1) return true;
	FOR(i,1,n) del[i]=false;
	if (build(1,len)) return true;
	return false;
}

int Getans(int l,int r,int p){
	while(l<=r){
		int m=(l+r)>>1;
		if (check(2*m+p)) l=m+1; else r=m-1;
	}
	return (l-1)*2+p;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen(name".inp","r",stdin);
	freopen(name".out","w",stdout);
	cin>>n;
	FOR(i,1,n) {
		char c; cin>>c;
		val[i]=c-'a'+1;
	}
	FOR(i,1,n-1){
		int u,v; cin>>u>>v;
		add_edge(u,v);
	}
	power[0]=1;
	FOR(i,1,n) power[i]=((LL)power[i-1]*base)%MOD;
	cout<<max(Getans(0,n,0),Getans(0,n,1));
}

Compilation message (stderr)

lampice.cpp: In function 'int32_t main()':
lampice.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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