Submission #1152010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152010		sasde	Lampice (COCI19_lampice)	C++20	0 / 110	5120 ms	291488 KiB

lampice

#include<bits/stdc++.h>
#define int long long
#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N=5e4+5,lg=20,mod=1e9+3,base=31;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int n,c[N],ans=1,sz[N],fup[N],fd[N],h[N],up[N][lg+5];
string s;
vector<int>a[N];
bool k[N];
void dfs(int u,int cha){
  sz[u]=1;
  for(int v:a[u]){
    if(v==cha||k[v])continue;
    dfs(v,u);
    sz[u]+=sz[v];
  }
}
int fin(int u,int cha,int n){
  for(int v:a[u]){
    if(v!=cha&&!k[v]&&sz[v]>n/2)return fin(v,u,n);

  }
  return u;
}
bool ok=false;
vector<int>node;
vector<ii>store[N];
void calc(int u,int cha){
  node.emb(u);
  store[h[u]].emb(fd[u],u);
  for(int j=1;j<=lg;++j)
    up[u][j]=up[up[u][j-1]][j-1];
  for(int v:a[u]){
    if(v==cha||k[v])continue;
    up[v][0]=u;
    h[v]=h[u]+1;
    fd[v]=(fd[u]*base+s[v]-'a'+1)%mod;
    fup[v]=(fup[u]+(s[v]-'a'+1)*c[h[u]])%mod;
    calc(v,u);
  }
}
int lift(int x,int k){
 for(int i=lg;i>=0;--i){
  if(k>=(1LL<<i)){
    k-=(1LL<<i);
    x=up[x][i];
  }
 }
 return x;
}
int gethash(int u,int v){
  return ((fd[u]-fd[up[v][0]]*c[h[u]-h[v]+1])%mod+mod)%mod;
}
int lca(int u,int v){
  if(h[u]<h[v])swap(u,v);
  for(int j=lg;j>=0;--j){
    if(h[u]-h[v]>=(1<<j))u=up[u][j];
  }
  if(u==v)return u;
   for(int j=lg;j>=0;--j){
    if(up[u][j]!=up[v][j]){
      u=up[u][j];
      v=up[v][j];
    }
   }

  return up[u][0];

}
void giai(int u,int cha,int mid){
    fup[u]=s[u]-'a'+1;
    fd[u]=s[u]-'a'+1;;
    node.clear();
    up[u][0]=0;
    h[u]=1;
    calc(u,cha);
    for(int i=1;i<=n;++i){
      if(store[i].empty())break;
      sort(store[i].begin(),store[i].end());
      // cout <<i<<" ";
    }
    // cout<<'\n';
    // cout <<node.size()<<" ";
    for(int i:node){
      if(ok)break;
      int dep=mid-h[i]+1;
      // cout <<i<<" "<<dep<<'\n';
      if(dep>h[i]||dep<1)continue;
      int X=lift(i,dep-1);
      if(fd[X]!=fup[X])continue;;
      int tmp=gethash(i,X);
      int l=lower_bound(store[dep].begin(),store[dep].end(),make_pair(tmp,0LL))-store[dep].begin();
      if(l==store[dep].size()||store[dep][l].fi!=tmp)continue;
      while(l<store[dep].size()){
        if(store[dep][l].fi!=tmp)break;
        if(lca(i,store[dep][l].se)==u){
          ok=true;
          break;
        }
        ++l;
      }
    }
    for(int i=1;i<=n;++i){
            if(store[i].empty())break;
      // sort(store[i].begin(),store[i].end());
            store[i].clear();
    }

}
void cen(int u,int cha,int mid){
  if(ok)return;
  // cout <<u<<" "
  // dfs(u,cha);
  // int g=fin(u,cha,sz[u]);
  // k[g]=true;
  // giai(g,u,mid);
  // for(int v:a[u]){
    // if(k[v]||v==cha)continue;
  // if(ok)return;

    // cen(v,u,mid);
  // }
}
int chatle(){
  int r=1,l=n/2;
  while(r<=l){
    for(int i=1;i<=n;++i)k[i]=false;
    ok=false;
    int mid=(r+l)/2;
    // cen(1,-1,mid*2+1);
    cout <<mid<<'\n';
    if(ok){
      ans=max(ans,mid*2+1);
      r=mid+1;
    }
    else l=mid-1;
  }
}
int chatchan(){
  int r=1,l=n/2;
  while(r<=l){
    ok=false;
    for(int i=1;i<=n;++i)k[i]=false;
    int mid=(r+l)/2;
    cen(1,-1,mid*2);

    if(ok){
      ans=max(ans,mid*2);
      r=mid+1;
    }
    else l=mid-1;
  }
}
void solve(){
  cin >> n >>s;
  for(int i=1;i<n;++i){
    int u,v;
    cin >> u >> v;
    a[u].emb(v);
    a[v].emb(u);
  }
  s=" "+s;
  c[0]=1;
  for(int i=1;i<=n;++i)c[i]=(c[i-1]*base)%mod;
    chatle();
    // chatchan();
  cout << ans;
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
    cout<<'\n';
}

}

Compilation message (stderr)

lampice.cpp: In function 'long long int chatle()':
lampice.cpp:158:1: warning: no return statement in function returning non-void [-Wreturn-type]
  158 | }
      | ^
lampice.cpp: In function 'long long int chatchan()':
lampice.cpp:173:1: warning: no return statement in function returning non-void [-Wreturn-type]
  173 | }
      | ^
lampice.cpp: At global scope:
lampice.cpp:189:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  189 | main()
      | ^~~~
lampice.cpp: In function 'int main()':
lampice.cpp:196:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:197:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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