Submission #764796

#	Time	Username	Problem	Language	Result	Execution time	Memory
764796		1075508020060209tc	Lampice (COCI19_lampice)	C++14	110 / 110	4844 ms	46332 KiB

lampice

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int qpow(int x,int t,int md){
if(t==0){return 1;}
if(t%2==1){return x*qpow(x,t-1,md)%md;}
int xx=qpow(x,t/2,md);
return xx*xx%md;
}
int n;
string s;
vector<int>e[150005];
int __id;
void adde(int a,int b){
__id++;
e[a].push_back(__id);
e[__id].push_back(a);
e[b].push_back(__id);
e[__id].push_back(b);
}
int mi;
const int mod[2]={998244353,1000000007};
int tme[1000006][2];int inv[1000006][2];
int okk;
int hsh[150005][2];
int rhsh[150005][2];
int dph[150005];
int sbsz[150005];
int vis[150005];
void dfssbsz(int nw,int pa,int &ctr,int fsz){
sbsz[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa||vis[v]){continue;}
    dfssbsz(v,nw,ctr,fsz);
    sbsz[nw]+=sbsz[v];
}
if(ctr==0&&sbsz[nw]*2>=fsz){
    ctr=nw;
}
}
unordered_map<int,int>mp[200005];
int rrt;int mxdph;int len;
void dfs(int nw,int pa,int typ){
    if(okk){return;}
    dph[nw]=dph[pa]+1;
if(typ==1){
    int c=hsh[nw][0];
    int d=rhsh[nw][0];
    int fv=(c*tme[len-dph[nw]][0]-d+mod[0])%mod[0];
    mp[dph[nw]][fv]=1;
}else{
    mxdph=max(mxdph,dph[nw]);
    hsh[nw][0]=(hsh[pa][0]+(s[nw]-'a')*tme[dph[nw]][0])%mod[0];
    rhsh[nw][0]=((s[nw]-'a')*tme[1][0]+rhsh[pa][0]*tme[1][0])%mod[0];
    if(dph[nw]<=len){
        int rv=(rhsh[nw][0]-(s[rrt]-'a')*tme[dph[nw]][0]%mod[0]+mod[0])%mod[0];
        int v=(hsh[nw][0]-(s[rrt]-'a')*tme[1][0]%mod[0]+mod[0])*inv[1][0]%mod[0];
        int fv=(v*tme[len-(dph[nw]-1)][0]-rv+mod[0])%mod[0];
        if(mp[len-(dph[nw]-1)].find(fv)!=mp[len-(dph[nw]-1)].end()){
            okk=1;
        }
    }
}
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa||vis[v]){continue;}
    dfs(v,nw,typ);
}
}
 
void decompose(int rt){
int ctr=0;
dfssbsz(rt,0,ctr,n);
ctr=0;
dfssbsz(rt,0,ctr,sbsz[rt]);
rrt=ctr;
//cout<<sbsz[rt]<<" "<<ctr<<endl;
hsh[ctr][0]=(s[ctr]-'a')*tme[1][0]%mod[0];
rhsh[ctr][0]=(s[ctr]-'a')*tme[1][0]%mod[0];
mxdph=0;
dph[ctr]=1;
    int c=hsh[ctr][0];
    int d=rhsh[ctr][0];
    int fv=(c*tme[mi*2+1-dph[ctr]][0]-d+mod[0])%mod[0];
    mp[1][fv]=1;
vis[ctr]=1;
for(int i=0;i<e[ctr].size();i++){
    int v=e[ctr][i];
    if(vis[v]){continue;}
    if(okk){return;}
    dfs(v,ctr,2);
    dfs(v,ctr,1);
}
/*
for(int i=1;i<=__id;i++){
    cout<<hsh[i][0]<<" ";
}cout<<endl;
for(int i=1;i<=__id;i++){
    cout<<rhsh[i][0]<<" ";
}cout<<endl;
*/
 
for(int i=0;i<=mxdph;i++){
    mp[i].clear();
}
if(okk){return;}
vis[ctr]=1;
for(int i=0;i<e[ctr].size();i++){
    int v=e[ctr][i];
    if(vis[v]){continue;}
    decompose(v);
}
}
 
int chk(int v){
mi=v;
len=mi*2+1;
for(int i=0;i<=__id;i++){
    vis[i]=0;
}
okk=0;
decompose(1);
return okk;
}
 
void precalc(){
tme[0][0]=1;
tme[0][1]=1;
for(int i=1;i<=200000;i++){
    tme[i][0]=tme[i-1][0]*37%mod[0];
    tme[i][1]=tme[i-1][1]*37%mod[1];
    inv[i][0]=qpow(tme[i][0],mod[0]-2,mod[0]);
    inv[i][1]=qpow(tme[i][1],mod[1]-2,mod[1]);
}
}
 
//1073
signed main(){
//cout<<'~'-'a'<<endl;
precalc();
cin>>n>>s;
s="*"+s;
for(int i=1;i<=n*3;i++){
    s+="~";
}
__id=n;
for(int i=1;i<=n-1;i++){
    int a;int b;
    cin>>a>>b;
    adde(a,b);
}
for(int i=1;i<=n;i++){
    if(e[i].size()==1){
        e[i].push_back(++__id);
        e[__id].push_back(i);
    }
}
/*
for(int i=1;i<=__id;i++){
    for(int j=0;j<e[i].size();j++){
        cout<<e[i][j]<<" ";
    }cout<<endl;
}
*/
 
int v;/*
while(cin>>v){
    cout<<chk(v)<<endl;
}*/
 
 
 
int l=1;int r=n;
 
while(l<r){
    int mi=l+(r-l+1)/2;
    if(chk(mi)){
        l=mi;
    }else{
        r=mi-1;
    }
}
 
 
cout<<l<<endl;
 
}

Compilation message (stderr)

lampice.cpp: In function 'void dfssbsz(long long int, long long int, long long int&, long long int)':
lampice.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs(long long int, long long int, long long int)':
lampice.cpp:67:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
lampice.cpp: In function 'void decompose(long long int)':
lampice.cpp:90:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 | for(int i=0;i<e[ctr].size();i++){
      |             ~^~~~~~~~~~~~~~
lampice.cpp:111:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 | for(int i=0;i<e[ctr].size();i++){
      |             ~^~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:169:5: warning: unused variable 'v' [-Wunused-variable]
  169 | int v;/*
      |     ^

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