oj.uz

Submission #1039147

# Submission time Handle Problem Language Result Execution time Memory
1039147 2024-07-30T13:44:23 Z cnn008 Lampice (COCI19_lampice) C++17
0 / 110
 1896 ms 14684 KB 
#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],mp2[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(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;
	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

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6748 KB Output is correct
2 Correct 8 ms 6748 KB Output is correct
3 Incorrect 21 ms 6920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 761 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1675 ms 13396 KB Output is correct
2 Incorrect 1896 ms 13144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6748 KB Output is correct
2 Correct 8 ms 6748 KB Output is correct
3 Incorrect 21 ms 6920 KB Output isn't correct
4 Halted 0 ms 0 KB -