Submission #1264516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264516		cattuong	Lampice (COCI19_lampice)	C++20	110 / 110	2112 ms	45600 KiB

lampice

/* I LOVE CATTUONG */
//
#include <bits/stdc++.h>
#define CatTuong ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
#define int long long
const int N=5e5+5;
const int base=311;
const int MOD=1e9+7;
string s;
int n,a[N],sz[N],h[N],suffH[N],preH[N],powB[N],H,mx_h,ans;
bool is_cen[N];
vector<int>g[N];
map<int,bool>mp[N];
int add(int x,int y){return (x+y)%MOD;}
int mul(int x,int y){return (x*y)%MOD;}
int sub(int x,int y){return ((x-y)+MOD)%MOD;}
void DFS(int u,int p){
    sz[u]=1;
    for(auto v:g[u]){
        if(v!=p && !is_cen[v]){
            DFS(v,u);
            sz[u]+=sz[v];
        }
    }
}
int find_cen(int u,int p,int tree_sz){
    for(auto v:g[u]){
        if(v!=p && !is_cen[v] && sz[v]>tree_sz/2)
            return find_cen(v,u,tree_sz);
    }
    return u;
}
bool get(int u,int p){
    h[u]=h[p]+1;
    if(h[u]>H)
        return 0;
    mx_h=max(mx_h,h[u]);
    preH[h[u]]=(preH[h[u]-1]*base + a[u])%MOD;
    suffH[h[u]]=(a[u]*powB[h[u]-1] + suffH[h[u]-1])%MOD;
    int tmp=(suffH[h[u]]*powB[H-h[u]] - preH[h[u]] + MOD)%MOD;
    if(suffH[h[u]]==preH[h[u]] && h[u]==H)
        return 1;
    if(mp[H-h[u]].find(tmp)!=mp[H-h[u]].end())
        return 1;
    for(auto v:g[u])
        if(v!=p && !is_cen[v])
            if(get(v,u))
                return 1;
    return 0;
}
void update(int u,int p){
    h[u]=h[p]+1;
    if(h[u]>H)
        return;
    mx_h=max(mx_h,h[u]);
    preH[h[u]]=(preH[h[u]-1]*base + a[u])%MOD;
    suffH[h[u]]=(a[u]*powB[h[u]-1] + suffH[h[u]-1])%MOD;
    int tmp=(suffH[h[u]]*powB[H-h[u]] - preH[h[u]] + MOD)%MOD;
    mp[h[u]][tmp]=1;
    for(auto v:g[u])
        if(v!=p && !is_cen[v])
            update(v,u);
}
bool build_cen(int u){
    DFS(u,-1);
    int cen=find_cen(u,-1,sz[u]);
    is_cen[cen]=1;
    mx_h=0;
    for(auto v:g[cen]){
        if(!is_cen[v]){
            h[cen]=1;
            suffH[1]=preH[1]=a[cen];
            if(get(v,cen))
                return 1;
            h[cen]=suffH[0]=preH[0]=0;
            update(v,cen);
        }
    }
    for(int i=0;i<=mx_h;i++)
        mp[i].clear();
    for(auto v:g[cen])
        if(!is_cen[v])
            if(build_cen(v))
                return 1;
    return 0;
}
bool check(int x){
    if(x>n) return 0;
    for(int i=1;i<=n;i++){
        mp[i].clear();
        is_cen[i]=0;
    }
    H=x;
    return build_cen(1);
}
signed main(){
    #define Tuong "LAMPICE"
//    freopen(Tuong".inp","r",stdin);
//    freopen(Tuong".out","w",stdout);
    CatTuong
    cin>>n>>s;
    for(int i=0;i<n;i++)
        a[i+1]=s[i]-'a'+1;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    powB[0]=1;
    for(int i=1;i<=n;i++)
        powB[i]=(powB[i-1]*base)%MOD;
    int lo=1,hi=n;ans=1;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(check(mid*2)){
            ans=max(ans,mid*2);
            lo=mid+1;
        }
        else
            hi=mid-1;
    }
    lo=1;hi=n;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(check(mid*2+1)){
            ans=max(ans,mid*2+1);
            lo=mid+1;
        }
        else
            hi=mid-1;
    }
    cout<<ans;
    return 0;
}

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