oj.uz

Submission #764796

# Submission time Handle Problem Language Result Execution time Memory
764796 2023-06-24T04:41:18 Z 1075508020060209tc Lampice (COCI19_lampice) C++14
110 / 110
 4844 ms 46332 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;
}
}
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

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

# Verdict Execution time Memory Grader output
1 Correct 197 ms 21196 KB Output is correct
2 Correct 203 ms 21224 KB Output is correct
3 Correct 218 ms 21452 KB Output is correct
4 Correct 228 ms 21572 KB Output is correct
5 Correct 196 ms 21040 KB Output is correct
6 Correct 195 ms 21008 KB Output is correct
7 Correct 195 ms 21068 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1859 ms 42972 KB Output is correct
2 Correct 1213 ms 43524 KB Output is correct
3 Correct 606 ms 43968 KB Output is correct
4 Correct 764 ms 45372 KB Output is correct
5 Correct 1826 ms 46332 KB Output is correct
6 Correct 408 ms 44760 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4141 ms 36696 KB Output is correct
2 Correct 3734 ms 35644 KB Output is correct
3 Correct 3644 ms 36636 KB Output is correct
4 Correct 3142 ms 37180 KB Output is correct
5 Correct 2575 ms 34428 KB Output is correct
6 Correct 2609 ms 33784 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 21196 KB Output is correct
2 Correct 203 ms 21224 KB Output is correct
3 Correct 218 ms 21452 KB Output is correct
4 Correct 228 ms 21572 KB Output is correct
5 Correct 196 ms 21040 KB Output is correct
6 Correct 195 ms 21008 KB Output is correct
7 Correct 195 ms 21068 KB Output is correct
8 Correct 1859 ms 42972 KB Output is correct
9 Correct 1213 ms 43524 KB Output is correct
10 Correct 606 ms 43968 KB Output is correct
11 Correct 764 ms 45372 KB Output is correct
12 Correct 1826 ms 46332 KB Output is correct
13 Correct 408 ms 44760 KB Output is correct
14 Correct 4141 ms 36696 KB Output is correct
15 Correct 3734 ms 35644 KB Output is correct
16 Correct 3644 ms 36636 KB Output is correct
17 Correct 3142 ms 37180 KB Output is correct
18 Correct 2575 ms 34428 KB Output is correct
19 Correct 2609 ms 33784 KB Output is correct
20 Correct 2742 ms 35136 KB Output is correct
21 Correct 3008 ms 41488 KB Output is correct
22 Correct 3537 ms 35532 KB Output is correct
23 Correct 2488 ms 34328 KB Output is correct
24 Correct 3868 ms 35524 KB Output is correct
25 Correct 2884 ms 35496 KB Output is correct
26 Correct 3837 ms 38608 KB Output is correct
27 Correct 4844 ms 36476 KB Output is correct
28 Correct 2576 ms 32760 KB Output is correct
29 Correct 2735 ms 33040 KB Output is correct
30 Correct 3398 ms 37584 KB Output is correct
31 Correct 4006 ms 34220 KB Output is correct
32 Correct 2643 ms 44212 KB Output is correct
33 Correct 2456 ms 37592 KB Output is correct