Submission #976955

#	Time	Username	Problem	Language	Result	Execution time	Memory
976955		boyliguanhan	Lampice (COCI19_lampice)	C++17	110 / 110	4442 ms	27100 KiB

lampice

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize(2)
gp_hash_table<int,int> mp[25010];
#define N 50010
#define int long long
int palin[N],vis[N],pw[N],hsh[N],sz[N],val[N],ans,rt,B=31,mod=1e9+7;
vector<int>adj[N],V{0};
void dfssz(int n,int p,int tot){
    palin[n]=0;
    int mx=0;
    sz[n]=1;
    for(auto i:adj[n])
        if(i-p&&!vis[i]) {
            dfssz(i,n,tot),
            sz[n]+=sz[i],
            mx=max(mx,sz[i]);
        }
    if(sz[n]*2>=tot&&mx*2<=tot)
        rt=n;
}
void dfshash(int n,int p){
    hsh[n]=(hsh[p]*B+val[n])%mod;
    for(auto i:adj[n])
        if(!vis[i]&&i-p)
            dfshash(i,n);
}
int MD;
void calcdfs(int n,int p,int l,int d,int h){
    MD=max(MD,d);
    if(d>l||ans) return;
    ans|=mp[d][(hsh[n]-val[V[1]]*pw[d]%mod+mod)%mod];
    h=(h+pw[d]*val[n])%mod;
    palin[n]=hsh[n]==h;
    for(auto i:adj[n])
        if(!vis[i]&&i-p)
            calcdfs(i,n,l,d+1,h);
}
void upddfs(int n,int p,int l,int d){
    if(ans||d>l) return;
    V.push_back(n);
    if(d+l/2>=l&&palin[V[2*d-l]])
        mp[l-d][(hsh[n]-hsh[V[2*d-l]]*pw[l-d]%mod+mod)%mod]=1;
    for(auto i:adj[n])
        if(i-p&&!vis[i])
            upddfs(i,n,l,d+1);
    V.pop_back();
}
void cent(int n,int s,int l){
    if(ans)
        return;
    MD=0;
    dfssz(n,0,s);
    dfssz(n=rt,0,s);
    palin[n]=1;
    dfshash(n,0);
    vis[n]=1;
    V.push_back(n);
    for(auto i:adj[n]) if(!vis[i])
        calcdfs(i,n,l,1,val[n]),
        upddfs(i,n,l,2);
    if(mp[0][0])
        ans=1;
    for(int i=0;i<=min(l/2,MD);i++)
        mp[i].clear();
    reverse(adj[n].begin(),adj[n].end());
    for(auto i:adj[n]) if(!vis[i])
        calcdfs(i,n,l,1,val[n]),
        upddfs(i,n,l,2);
    if(mp[0][0])
        ans=1;
    for(int i=0;i<=min(l/2,MD);i++)
        mp[i].clear();
    V.pop_back();
    for(auto i:adj[n])
        if(!vis[i])
            cent(i,sz[i],l);
}
signed main() {
    pw[0]=1;
    for(int i=1;i<N;i++)
        pw[i]=pw[i-1]*B%mod;
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string str;
    cin>>n>>str;
    for(int i=1;i<=n;i++)
        val[i]=str[i-1]-'`';
    if(n==1)
        return puts("1"),0;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int l=0,r=n/2,CALLS=0;
    while(l<r){
        int mid=l+r+1>>1;
        for(int i=1;i<=n;i++)
            palin[i]=vis[i]=ans=0;
        cent(1,n,mid*2+1);
        CALLS++;
        if(ans)
            l=mid;
        else r=mid-1;
    }
    int l1=l,r1=n/2;
    while(l1<r1){
        int mid=l1+r1+1>>1;
        for(int i=1;i<=n;i++)
            palin[i]=vis[i]=ans=0;
        cent(1,n,mid*2);
        CALLS++;
        if(ans)
            l1=mid;
        else r1=mid-1;
    }
    cout<<max(l1*2,l*2+1)<<'\n';
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:101:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:112:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

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