Submission #1023325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023325		doducanh	Lampice (COCI19_lampice)	C++14	110 / 110	2109 ms	11792 KiB

lampice

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e4+7;
const int mod=1e9+7;
const int base=9973;
int lo[maxn];
vector<int>adj[maxn];
int subsz[maxn];
bool removed[maxn];
int dis[maxn];
int color[maxn];
int curdn[maxn];
int down[maxn];
bool pal[maxn];
int up[maxn];
bool bb=0;
vector<int>toadd_l,toadd_s;
set<int>hashl,hashs;
string s;
int n;
int curlen;
int get(int l,int r,int x,int y){
    return (y-(lo[(r-l)]*x)%mod+2*mod)%mod;
}
int get_subsize(int u,int par){
    subsz[u]=1;
    for(int v:adj[u]){
        if(removed[v]||v==par)continue;
        get_subsize(v,u);
        subsz[u]+=subsz[v];
    }
    return subsz[u];
}
int find_cen(int u,int par,int treesize){
    for(int v:adj[u]){
        if(removed[v]||v==par)continue;
        if((subsz[v]*2)>treesize)return find_cen(v,u,treesize);
    }
    return u;
}
void dfs(int u,int par){
    if(bb)return;
    dis[u]=dis[par]+1;
    if(dis[u]>curlen)return;
    curdn[dis[u]]=u;
    down[u]=(down[par]*base%mod+color[u])%mod;
    up[u]=(up[par]+color[u]*lo[dis[u]]%mod)%mod;
    pal[u]=(down[u]==up[u]);
    if(dis[u]==curlen){
        bb=pal[u];
    }
    else if(dis[u]>curlen/2){
        int diff=dis[u]*2-curlen;
        int c=curdn[diff];
        if(pal[c]){
            int hn=get(dis[c]-1,dis[u],down[curdn[diff-1]],down[u]);
            if(hashs.count(hn))bb=1;
            toadd_l.push_back(hn);
        }
    }
    else{
        if(hashl.count(down[u]))bb=1;
        toadd_s.push_back(down[u]);
    }
    if(dis[u]*2==curlen){
        if(hashs.count(down[u]))bb=1;
    }

    for(int v:adj[u]){
        if(v==par||removed[u])continue;
        dfs(v,u);
    }

}
void centroid_decomp(int u=1){
    if(bb)return;
    int cen=find_cen(u,0,get_subsize(u,0));
    removed[cen]=1;
    curdn[0]=cen;
    dis[cen]=0;
    down[cen]=color[cen];
    up[cen]=color[cen];
    for(int v:adj[cen]){
        if(removed[v])continue;
        dfs(v,cen);
        for(int x:toadd_l)hashl.insert(x);
        for(int x:toadd_s)hashs.insert(x);
        toadd_l.clear();
        toadd_s.clear();
    }
    hashl.clear();
    hashs.clear();
    for(int v:adj[cen]){
        if(removed[v]==0){
            centroid_decomp(v);
        }
    }

}
bool check(int length){
    if(length==1)return true;
    curlen=length-1;
    for(int i=1;i<=n;i++)removed[i]=0;
    bb=0;
    centroid_decomp();
    return bb;
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    lo[0]=1;
    for(int i=1;i<=n;i++)lo[i]=(lo[i-1]*base)%mod;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++)color[i]=s[i]-'a'+1;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    //odd len
    int l=0,r=n/2-((n%2)==0);
    int res=0;
    while(l<=r){
        int m=(l+r)/2;
        if(check(2*m+1)){
            res=max(res,2*m+1);
            l=m+1;
        }
        else r=m-1;
    }

    l=(res)/2+1,r=n/2;
    while(l<=r){
        int m=(l+r)/2;
        if(check(2*m)){
            res=max(res,2*m);
            l=m+1;
        }
        else r=m-1;
    }
    cout<<res;
}

Compilation message (stderr)

lampice.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~

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