Submission #1153344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153344		son2008	Lampice (COCI19_lampice)	C++20	17 / 110	5091 ms	29172 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],h[maxn],q,par[maxn],ans=2e9,mn[maxn],mx_h,k,s[maxn],pw[maxn],H;
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,int h,int down,int up)
{
    mx_h=max(mx_h,h);
    if(h>H)return false;
    down=(1LL*down*base+1LL*s[u])%mod;
    up=(1LL*s[u]*pw[h-1]+1LL*up)%mod;
    int x=(1LL*up*pw[H-h]-1LL*down+mod)%mod;
 //   cout<<0<<" "<<down<<" "<<up<<" "<<h<<" "<<x<<" "<<d[h][x]<<'\n';
    if(d[H-h][x])return true;
    if(up==down&&h==H)return true;
    for(int v:a[u])
    {
        if(v==cha||is_centroid[v])continue;
        if(get(v,u,h+1,down,up))return true;
    }
    return false;
}
void update(int u,int cha,int h,int down,int up)
{
    mx_h=max(mx_h,h);
    if(h>H)return;
    down=(1LL*down*base+1LL*s[u])%mod;
    up=(1LL*s[u]*pw[h-1]+1LL*up)%mod;
    int x=(1LL*up*pw[H-h]-1LL*down+mod)%mod;
    d[h][x]=true;
    //cout<<1<<" "<<down<<" "<<up<<" "<<h<<" "<<x<<'\n';
    for(int v:a[u])
    {
        if(v==cha||is_centroid[v])continue;
        update(v,u,h+1,down,up);
    }
}
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])
        {
            if(get(v,centroid,2,s[centroid],s[centroid]))return true;
            update(v,centroid,1,0,0);
        }
    }
    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:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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