Submission #764792

# Submission time Handle Problem Language Result Execution time Memory
764792 2023-06-24T04:34:10 Z 1075508020060209tc Lampice (COCI19_lampice) C++14
17 / 110
5000 ms 59320 KB
#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;
}
}
map<int,int>mp[200005];
int rrt;int mxdph;
void dfs(int nw,int pa,int typ){
dph[nw]=dph[pa]+1;
if(typ==1){
    int c=hsh[nw][0];
    int d=rhsh[nw][0];
    int fv=(c*tme[mi*2+1-dph[nw]][0]-d+mod[0])%mod[0];
    mp[dph[nw]][fv]=1;
}else{
    if(dph[nw]<=mi*2+1){
        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];
        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[mi*2+1-(dph[nw]-1)][0]-rv+mod[0])%mod[0];
        if(mp[mi*2+1-(dph[nw]-1)].find(fv)!=mp[mi*2+1-(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;
for(int i=0;i<e[ctr].size();i++){
    int v=e[ctr][i];
    if(vis[v]){continue;}
    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;
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

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:66: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]
   66 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
lampice.cpp: In function 'void decompose(long long int)':
lampice.cpp:88: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]
   88 | for(int i=0;i<e[ctr].size();i++){
      |             ~^~~~~~~~~~~~~~
lampice.cpp:108: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]
  108 | for(int i=0;i<e[ctr].size();i++){
      |             ~^~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:165:5: warning: unused variable 'v' [-Wunused-variable]
  165 | int v;/*
      |     ^
# Verdict Execution time Memory Grader output
1 Correct 205 ms 19532 KB Output is correct
2 Correct 206 ms 19724 KB Output is correct
3 Correct 239 ms 19952 KB Output is correct
4 Correct 252 ms 20052 KB Output is correct
5 Correct 203 ms 19404 KB Output is correct
6 Correct 193 ms 19604 KB Output is correct
7 Correct 195 ms 19416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2288 ms 59320 KB Output is correct
2 Incorrect 2197 ms 40224 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4950 ms 48568 KB Output is correct
2 Correct 4743 ms 36084 KB Output is correct
3 Execution timed out 5048 ms 35676 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 205 ms 19532 KB Output is correct
2 Correct 206 ms 19724 KB Output is correct
3 Correct 239 ms 19952 KB Output is correct
4 Correct 252 ms 20052 KB Output is correct
5 Correct 203 ms 19404 KB Output is correct
6 Correct 193 ms 19604 KB Output is correct
7 Correct 195 ms 19416 KB Output is correct
8 Correct 2288 ms 59320 KB Output is correct
9 Incorrect 2197 ms 40224 KB Output isn't correct
10 Halted 0 ms 0 KB -