oj.uz

Submission #1039171

# Submission time Handle Problem Language Result Execution time Memory
1039171 2024-07-30T14:01:39 Z cnn008 Lampice (COCI19_lampice) C++17
110 / 110
 2132 ms 13620 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];
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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4184 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 21 ms 4444 KB Output is correct
4 Correct 19 ms 4900 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4300 KB Output is correct
7 Correct 2 ms 4740 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 12208 KB Output is correct
2 Correct 750 ms 12540 KB Output is correct
3 Correct 522 ms 12808 KB Output is correct
4 Correct 634 ms 13392 KB Output is correct
5 Correct 1029 ms 13620 KB Output is correct
6 Correct 105 ms 11868 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 11168 KB Output is correct
2 Correct 2086 ms 10896 KB Output is correct
3 Correct 1706 ms 11048 KB Output is correct
4 Correct 1665 ms 9960 KB Output is correct
5 Correct 1399 ms 10324 KB Output is correct
6 Correct 1232 ms 9912 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4184 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 21 ms 4444 KB Output is correct
4 Correct 19 ms 4900 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4300 KB Output is correct
7 Correct 2 ms 4740 KB Output is correct
8 Correct 829 ms 12208 KB Output is correct
9 Correct 750 ms 12540 KB Output is correct
10 Correct 522 ms 12808 KB Output is correct
11 Correct 634 ms 13392 KB Output is correct
12 Correct 1029 ms 13620 KB Output is correct
13 Correct 105 ms 11868 KB Output is correct
14 Correct 1774 ms 11168 KB Output is correct
15 Correct 2086 ms 10896 KB Output is correct
16 Correct 1706 ms 11048 KB Output is correct
17 Correct 1665 ms 9960 KB Output is correct
18 Correct 1399 ms 10324 KB Output is correct
19 Correct 1232 ms 9912 KB Output is correct
20 Correct 1147 ms 8536 KB Output is correct
21 Correct 1378 ms 9552 KB Output is correct
22 Correct 2132 ms 10132 KB Output is correct
23 Correct 400 ms 7472 KB Output is correct
24 Correct 1467 ms 8784 KB Output is correct
25 Correct 1372 ms 8540 KB Output is correct
26 Correct 1729 ms 10820 KB Output is correct
27 Correct 2058 ms 10520 KB Output is correct
28 Correct 1102 ms 7516 KB Output is correct
29 Correct 1157 ms 7792 KB Output is correct
30 Correct 1260 ms 9556 KB Output is correct
31 Correct 1105 ms 8452 KB Output is correct
32 Correct 1127 ms 10588 KB Output is correct
33 Correct 1042 ms 10324 KB Output is correct