Submission #844078

#	Time	Username	Problem	Language	Result	Execution time	Memory
844078		Caubethieunang	Lampice (COCI19_lampice)	C++17	110 / 110	2274 ms	21500 KiB

lampice

#include <bits/stdc++.h>
#define ll long long
#define LOG 20
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
#define ERASE_BIT(mask) (mask)^((mask)&(-mask))
#define left _left
#define right _right
#define task "t"
using namespace std;
const ll INF=1e18;
const int iat=1e5+9;
const int mod=1e9+7;
const int base=31;
void fast_IO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}
int n;
char s[iat];
vector <int> g[iat],node;
int child[iat],dep[iat],f[iat][LOG];
bool visited[iat],res;
ll pw[iat],HashUp[iat],HashDown[iat];
vector <pair<ll,int>> store[iat];
void dfs(int u, int par)
{
    child[u]=1;
    for(auto v : g[u])
    {
        if(v!=par && !visited[v])dfs(v,u),child[u]+=child[v];
    }
}
int centroid(int u, int par, int sz)
{
    for(auto v : g[u])
    {
        if(v!=par && !visited[v])
        {
            if(child[v]>sz/2)return centroid(v,u,sz);
        }
    }
    return u;
}
void calc(int u, int par)
{
    node.push_back(u);
    store[dep[u]].push_back(make_pair(HashDown[u],u));
    for(int i=1; MASK(i)<=n; i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int v : g[u])
    {
        if(v!=par && !visited[v])
        {
            f[v][0]=u;
            dep[v]=dep[u]+1;
            HashDown[v]=HashDown[u]*base+s[v]-'a'+1;
            HashUp[v]=HashUp[u]+pw[dep[v]-1]*(s[v]-'a'+1);
            calc(v,u);
        }
    }
}
int lift(int x, int k)
{
    for(int i=LOG-1; i>=0; i--)
    {
        if(BIT(k,i))x=f[x][i];
    }
    return x;
}
int LCA(int u, int v)
{
    if(u==v)return u;
    if(dep[u]<dep[v])swap(u,v);
    int k=dep[u]-dep[v];
    for(int i=LOG-1; i>=0; i--)
    {
        if(BIT(k,i))u=f[u][i];
    }
    if(u==v)return u;
    for(int i=LOG-1; i>=0; i--)
    {
        if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    }
    return f[u][0];
}
ll GetHash(int u, int v)
{
  return HashDown[u]-HashDown[f[v][0]]*pw[dep[u]-dep[v]+1];
}
void solve(int u, int len)
{
    if(res)return;
    HashUp[u]=s[u]-'a'+1;
    HashDown[u]=s[u]-'a'+1;
    node.clear();
    f[u][0]=0,dep[u]=1;
    calc(u,u);
    for(int i=1; i<=n; i++)
    {
        if(store[i].empty())break;
        sort(store[i].begin(),store[i].end());
    }
    for(int it : node)
    {
        if(res)break;
        int dneed=len-dep[it]+1;
        if(dneed>dep[it] || dneed<1)continue;
        int X=lift(it,dneed-1);
        if(HashDown[X]!=HashUp[X])continue;
        ll tmp=GetHash(it,X);
        int l=lower_bound(store[dneed].begin(),store[dneed].end(),make_pair(tmp,-1))-store[dneed].begin();
        if(l==store[dneed].size() || store[dneed][l].first!=tmp)continue;
        while(l<store[dneed].size())
        {
            if(store[dneed][l].first!=tmp)break;
            if(LCA(it,store[dneed][l].second)==u)
            {
                res=true;
                break;
            }
            l++;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(store[i].empty())break;
        store[i].clear();
    }
}
void build_tree(int u, int len)
{
    if(res)return;
    dfs(u,u);
    int x=centroid(u,u,child[u]);
    visited[x]=true;
    solve(x,len);
    for(int v : g[x])
    {
        if(!visited[v])build_tree(v,len);
    }
}
bool check(int x)
{
    for(int i=1; i<=n; i++)visited[i]=false;
    res=false;
    build_tree(1,x);
    return res;
}
signed main()
{
    fast_IO();
    cin>>n;
    pw[0]=1;
    for(int i=1; i<=n; i++)pw[i]=pw[i-1]*base;
    for(int i=1; i<=n; i++)cin>>s[i];
    for(int i=1; i<n; i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans=1;
    int l=1,r=n/2;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int val=mid*2+1;
        if(check(val))ans=max(ans,val),l=mid+1;
        else r=mid-1;
    }
    l=1,r=n/2;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int val=mid*2;
        if(check(val))ans=max(ans,val),l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
}

Compilation message (stderr)

lampice.cpp: In function 'void solve(int, int)':
lampice.cpp:120:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if(l==store[dneed].size() || store[dneed][l].first!=tmp)continue;
      |            ~^~~~~~~~~~~~~~~~~~~~~
lampice.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while(l<store[dneed].size())
      |               ~^~~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'void fast_IO()':
lampice.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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