oj.uz

Submission #844078

# Submission time Handle Problem Language Result Execution time Memory
844078 2023-09-05T07:00:28 Z Caubethieunang Lampice (COCI19_lampice) C++17
110 / 110
 2274 ms 21500 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10072 KB Output is correct
2 Correct 8 ms 10072 KB Output is correct
3 Correct 18 ms 10076 KB Output is correct
4 Correct 24 ms 10324 KB Output is correct
5 Correct 2 ms 7768 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 18516 KB Output is correct
2 Correct 924 ms 18708 KB Output is correct
3 Correct 664 ms 18904 KB Output is correct
4 Correct 769 ms 21208 KB Output is correct
5 Correct 1266 ms 21496 KB Output is correct
6 Correct 218 ms 21500 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2274 ms 18780 KB Output is correct
2 Correct 2192 ms 18380 KB Output is correct
3 Correct 1979 ms 18812 KB Output is correct
4 Correct 2017 ms 18948 KB Output is correct
5 Correct 1373 ms 15876 KB Output is correct
6 Correct 1542 ms 15820 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10072 KB Output is correct
2 Correct 8 ms 10072 KB Output is correct
3 Correct 18 ms 10076 KB Output is correct
4 Correct 24 ms 10324 KB Output is correct
5 Correct 2 ms 7768 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 1327 ms 18516 KB Output is correct
9 Correct 924 ms 18708 KB Output is correct
10 Correct 664 ms 18904 KB Output is correct
11 Correct 769 ms 21208 KB Output is correct
12 Correct 1266 ms 21496 KB Output is correct
13 Correct 218 ms 21500 KB Output is correct
14 Correct 2274 ms 18780 KB Output is correct
15 Correct 2192 ms 18380 KB Output is correct
16 Correct 1979 ms 18812 KB Output is correct
17 Correct 2017 ms 18948 KB Output is correct
18 Correct 1373 ms 15876 KB Output is correct
19 Correct 1542 ms 15820 KB Output is correct
20 Correct 1249 ms 15432 KB Output is correct
21 Correct 1174 ms 15356 KB Output is correct
22 Correct 1660 ms 15816 KB Output is correct
23 Correct 1045 ms 15512 KB Output is correct
24 Correct 1628 ms 19124 KB Output is correct
25 Correct 1709 ms 18592 KB Output is correct
26 Correct 1887 ms 18892 KB Output is correct
27 Correct 2172 ms 18164 KB Output is correct
28 Correct 1570 ms 18136 KB Output is correct
29 Correct 1627 ms 18224 KB Output is correct
30 Correct 1668 ms 19392 KB Output is correct
31 Correct 1551 ms 18416 KB Output is correct
32 Correct 1256 ms 19960 KB Output is correct
33 Correct 966 ms 17620 KB Output is correct