This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e4+1;
const int mod=1e9+7;
int h[maxn],n;
char s[maxn];
vector<int>a[maxn];
void dfs(int u,int cha)
{
for(int v:a[u])
{
if(v==cha)continue;
h[v]=h[u]+1;
dfs(v,u);
}
}
namespace sub2
{
int h[50068],p[50068],hr[50068];
int getl(int l,int r){
return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod;
}
int getr(int i, int j) {
return (hr[i] - hr[j+1] * p[j-i+1]%mod+mod)%mod;
}
bool check(int i,int j){
return (getl(i,j)==getr(i,j));
}
void solve(void)
{
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=(h[i-1]*base+s[i]-'a'+1)%mod;
p[i]=(p[i-1]*base)%mod;
}
for(int i=n;i>=1;i--)
hr[i]=(hr[i+1]*base+s[i]-'a'+1)%mod;
int ans=0;
for(int i=1;i<=n;i++){
int l=0,r=min(n-i,i);
while(l<=r){
int mid=(l+r)/2;
if(check(i-mid+1,i+mid)){
ans=max(ans,mid*2);
l=mid+1;
}
else
r=mid-1;
}
l=0,r=min(i-1,n-i);
while(l<=r){
int mid=(l+r)/2;
if(check(i-mid,i+mid)){
ans=max(ans,mid*2+1);
l=mid+1;
}
else
r=mid-1;
}
}
cout<<ans;
}
}
namespace sub1
{
int ans=0;
bool check(string s)
{
int l=0,r=s.size()-1;
while(l<r)
{
if(s[l]!=s[r])return false;
l++;
r--;
}
return true;
}
bool dfs(int u,int cha,string tmp,int dem)
{
tmp+=s[u];
bool ok=false;
for(int v:a[u])
{
if(v==cha)continue;
if(dfs(v,u,tmp,dem+1))ok=true;
}
if(ok)return true;
else
{
if(ans>=dem)return true;
else if(check(tmp))
{
ans=dem;
return true;
}
else return false;
}
}
void solve(void)
{
for(int i=1;i<=n;i++)
{
dfs(i,-1,"",1);
}
cout<<ans;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);}
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,-1);
if(h[n]==n-1)sub2::solve();
else sub1::solve();
cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}
Compilation message (stderr)
lampice.cpp: In function 'int main()':
lampice.cpp:130:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:131:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | freopen(task".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |