Submission #1264496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264496		cattuong	Lampice (COCI19_lampice)	C++20	0 / 110	286 ms	13944 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
//suff:abc pre:cba
// palin suff*pow[h-x]-pre
const int N=5e4+5;
const int MOD=1e9+7;
const int base=32;
int sz[N],heavy[N],mx_h,powB[N],n,ans;
char a[N];
bool is_cen[N];
unordered_map<int,bool>mp[N];
vector<int>g[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;
    int mx_son_sz=0;
    for(auto v:g[u]){
        if(v!=p && !is_cen[v]){
            DFS(v,u);
            sz[u]+=sz[v];
            if(sz[v]>mx_son_sz){
                mx_son_sz=sz[v];
                heavy[u]=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,int cur_h,int cur_pre_hash,int cur_suff_hash,int &H){
    if(cur_h>mx_h)
        return 0;
    H=max(H,cur_h);
    int preH=add(mul(cur_pre_hash,base),a[u]);
    int suffH=add(mul(a[u],powB[cur_h-1]),cur_suff_hash);
    int tmp=sub(mul(suffH,powB[H-cur_h]),preH);
    if(suffH==preH && cur_h==mx_h)
        return 1;
    if(mp[mx_h-cur_h].find(tmp)!=mp[mx_h-cur_h].end())
        return 1;
    for(auto v:g[u]){
        if(v!=p && !is_cen[v])
            if(get(v,u,cur_h+1,preH,suffH,H))
                return 1;
    }
    return 0;
}
void update(int u,int p,int cur_h,int cur_pre_hash,int cur_suff_hash,int &H){
    if(cur_h>H)
        return;
    H=max(H,cur_h);
    int preH=add(mul(cur_pre_hash,base),a[u]);
    int suffH=add(mul(a[u],powB[cur_h-1]),cur_suff_hash);
    int tmp=sub(mul(suffH,powB[H-cur_h]),preH);
    mp[cur_h][tmp]=1;
    for(auto v:g[u]){
        if(v!=p && !is_cen[v])
            update(v,u,cur_h+1,preH,suffH,H);
    }
}
bool build_cen(int u){
    DFS(u,-1);
    int cen=find_cen(u,-1,sz[u]);
    is_cen[cen]=true;
    int H=0;
    for(auto v:g[cen]){
        if(v!=cen && !is_cen[v]){
            if(get(v,cen,2,a[cen],a[cen],H))
                return 1;
            update(v,cen,1,0,0,H);
        }
    }
    for(int i=0;i<=H;++i){
        mp[i].clear();
    }
    for(auto v:g[cen]){
        if(!is_cen[v]){
           return build_cen(v);
        }
    }
    return 0;
}
int check(int x){
    for(int i=1;i<=n;++i){
        mp[i].clear();
        is_cen[i]=false;
    }
    mx_h=x;
    return build_cen(1);
}
signed main(){
    #define Tuong "Lampice"
//    freopen(Tuong".inp","r",stdin);
//    freopen(Tuong".out","w",stdout);
    CatTuong
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    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]=mul(powB[i-1],base);
    }
    int lo=0,hi=n;
    while(hi>=lo){
        int mid=(hi+lo)>>1;
        if(2*mid<=n){
            if(check(2*mid)){
                ans=2*mid;
                lo=mid+1;
            }
            else
                hi=mid-1;
        }
        else
            hi=mid-1;
    }
    lo=0,hi=n;
    while(hi>=lo){
        int mid=(hi+lo)>>1;
        if(2*mid+1<=n){
            if(check(2*mid+1)){
                ans=max(ans,2*mid+1);
                lo=mid+1;
            }
            else
                hi=mid-1;
        }
        else
            hi=mid-1;
    }
    cout<<ans;
    return 0;
}

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