Submission #1153350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153350		son2008	Lampice (COCI19_lampice)	C++20	42 / 110	5094 ms	35080 KiB

lampice

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 31
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e4+5;
const int mod=1e9+7;
int n,root,sz[maxn],q,ans=2e9,mx_h,k,s[maxn],pw[maxn],H,up[maxn],down[maxn],h[maxn];
bool is_centroid[maxn];
vector<int>a[maxn];
void dfs(int u,int cha)
{
    sz[u]=1;
    for(int v:a[u])
    {
        if(v==cha||is_centroid[v])continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int find_centroid(int u,int tree_sz,int cha)
{
    for(int v:a[u])
        if(v!=cha&&!is_centroid[v]&&sz[v]>tree_sz/2) return find_centroid(v,tree_sz,u);
    return u;
}
map<int,bool>d[maxn];
bool get(int u,int cha)
{
    h[u]=h[cha]+1;
    mx_h=max(mx_h,h[u]);
    if(h[u]>H)return false;
    down[h[u]]=(1LL*down[h[u]-1]*base+s[u])%mod;
    up[h[u]]=(1LL*s[u]*pw[h[u]-1]+up[h[u]-1])%mod;
    int x=(1LL*up[h[u]]*pw[H-h[u]]-down[h[u]]+mod)%mod;
    if(up[h[u]]==down[h[u]]&&h[u]==H)return true;
    if(d[H-h[u]][x])return true;
    for(int v:a[u])
    {
        if(v==cha||is_centroid[v])continue;
        if(get(v,u))return true;
    }
    return false;
}
void update(int u,int cha)
{
    h[u]=h[cha]+1;
    mx_h=max(mx_h,h[u]);
    if(h[u]>H)return;
    down[h[u]]=(1LL*down[h[u]-1]*base+s[u])%mod;
    up[h[u]]=(1LL*s[u]*pw[h[u]-1]+up[h[u]-1])%mod;
    int x=(1LL*up[h[u]]*pw[H-h[u]]-down[h[u]]+mod)%mod;
    d[h[u]][x]=true;
    for(int v:a[u])
    {
        if(v==cha||is_centroid[v])continue;
        update(v,u);
    }
}
bool build_centroid(int u,int pre_centroid)
{
    dfs(u,-1);
    int centroid=find_centroid(u,sz[u],-1);
    if(root==0)root=centroid;
    mx_h=0;
    is_centroid[centroid]=true;
    for(int v:a[centroid])
    {
        if(!is_centroid[v])
        {
            h[centroid]=1,up[1]=down[1]=s[centroid];
            if(get(v,centroid))return true;
            h[centroid]=up[0]=down[0]=0;
            update(v,centroid);
        }
    }
    for(int i=0;i<=mx_h;i++)d[i].clear();
    for(int v:a[centroid])
    {
        if(!is_centroid[v])if(build_centroid(v,centroid))return true;
    }
    return false;
}
bool check(int mid)
{
    if(mid>n)return false;
    for(int i=1;i<=n;i++)d[i].clear(),is_centroid[i]=false;
    H=mid;
    return build_centroid(1,-1);
}
void init()
{
    string c;
    cin>>n>>c;
    for(int i=0;i<n;i++)
    {
        s[i+1]=c[i]-'a'+1;
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=(1LL*pw[i-1]*base)%mod;
}
void process()
{
    int ans=1;
    int l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(2*mid))
        {

            ans=max(ans,2*mid);
            l=mid+1;
        }
        else r=mid-1;
    }
    l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(2*mid+1))
        {
            ans=max(ans,2*mid+1);
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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