#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
const int INF=1000000000;
int edges[300005][26];
int backedge[300005];
int len[300005];
int PREV=0;
int INDEX=1;
int n;
string s;
vector<int> al[3005];
int parent[3005][15];
int level[3005]; //depth idk why i used to call it level
int in[3005];
int out[3005];
int DFS_TIME=0;
void dfs(int i,int p){
in[i]=++DFS_TIME;
int curr;
for (auto it=al[i].begin();it!=al[i].end();it++){
if (*it==p) continue;
level[*it]=level[i]+1;
parent[*it][0]=i;
curr=i;
for (int x=0;parent[curr][x]!=-1;x++){
curr=parent[*it][x+1]=parent[curr][x];
}
dfs(*it,i);
}
out[i]=DFS_TIME;
}
int mov(int i,int j){
for (int x=0;x<22;x++){
if (j&1){
i=parent[i][x];
}
j>>=1;
}
return i;
}
int lca(int i,int j){
if (level[i]<level[j]) swap(i,j);
i=mov(i,level[i]-level[j]);
if (i==j) return i;
for (int x=21;x>=0;x--){
if (parent[i][x]!=parent[j][x]){
i=parent[i][x];
j=parent[j][x];
}
}
return parent[i][0];
}
int dist(int i,int j){
return level[i]+level[j]-2*level[lca(i,j)];
}
int memo[3005][3005];
int dp(int i,int j){
if (memo[i][j]!=-1) return memo[i][j];
if (s[i]!=s[j]) return -INF;
if (level[i]>level[j]) swap(i,j); //i could be ancestor of j
if (i==j) return memo[i][j]=1;
else if (parent[j][0]==i) return memo[i][j]=2;
else{
if (in[i]<=in[j] && out[j]<=out[j]){
return dp(mov(j,level[j]-level[i]-1),parent[j][0])+2;
}
else{
return dp(parent[i][0],parent[j][0])+2;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>s;
if (n<=3000){
int a,b;
for (int x=1;x<n;x++){
cin>>a>>b;
a--,b--;
al[a].push_back(b);
al[b].push_back(a);
}
memset(parent,-1,sizeof(parent));
dfs(0,-1);
int ans=0;
memset(memo,-1,sizeof(memo));
for (int x=0;x<n;x++)
for (int y=0;y<n;y++)
ans=max(ans,dp(x,y));
cout<<ans<<endl;
}
else{
int ans=0;
memset(edges,-1,sizeof(edges));
backedge[0]=0,backedge[1]=0;
len[0]=-1,len[1]=0;
for (int x=0;x<s.size();x++){
while (s[x-len[PREV]-1]!=s[x])
PREV=backedge[PREV];
if (edges[PREV][s[x]-'a']==-1)
edges[PREV][s[x]-'a']=++INDEX;
int curr=edges[PREV][s[x]-'a'];
len[curr]=len[PREV]+2;
ans=max(ans,len[curr]);
if (len[curr]==1){
backedge[curr]=1;
}
else{
int b=backedge[PREV];
while (s[x-len[b]-1]!=s[x]) b=backedge[b];
backedge[curr]=edges[b][s[x]-'a'];
}
PREV=curr;
}
cout<<ans<<endl;
}
}
Compilation message
lampice.cpp: In function 'int dp(int, int)':
lampice.cpp:84:29: warning: self-comparison always evaluates to true [-Wtautological-compare]
if (in[i]<=in[j] && out[j]<=out[j]){
~~~~~~^~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int x=0;x<s.size();x++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
35968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
31104 KB |
Output is correct |
| 2 |
Correct |
23 ms |
31360 KB |
Output is correct |
| 3 |
Correct |
21 ms |
31616 KB |
Output is correct |
| 4 |
Correct |
22 ms |
31616 KB |
Output is correct |
| 5 |
Correct |
22 ms |
31488 KB |
Output is correct |
| 6 |
Correct |
22 ms |
31744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
31360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
35968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
