oj.uz

답안 #764788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764788 2023-06-24T04:31:08 Z 1075508020060209tc Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 42388 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;
    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(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){
        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;/*
      |     ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 19620 KB Output is correct
2 Correct 207 ms 19616 KB Output is correct
3 Correct 240 ms 19912 KB Output is correct
4 Correct 263 ms 19940 KB Output is correct
5 Correct 199 ms 19360 KB Output is correct
6 Correct 196 ms 19496 KB Output is correct
7 Correct 196 ms 19480 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2625 ms 39356 KB Output is correct
2 Correct 2644 ms 39864 KB Output is correct
3 Correct 2720 ms 40372 KB Output is correct
4 Correct 2757 ms 41376 KB Output is correct
5 Correct 3053 ms 42388 KB Output is correct
6 Correct 2055 ms 39260 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5061 ms 36468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 19620 KB Output is correct
2 Correct 207 ms 19616 KB Output is correct
3 Correct 240 ms 19912 KB Output is correct
4 Correct 263 ms 19940 KB Output is correct
5 Correct 199 ms 19360 KB Output is correct
6 Correct 196 ms 19496 KB Output is correct
7 Correct 196 ms 19480 KB Output is correct
8 Correct 2625 ms 39356 KB Output is correct
9 Correct 2644 ms 39864 KB Output is correct
10 Correct 2720 ms 40372 KB Output is correct
11 Correct 2757 ms 41376 KB Output is correct
12 Correct 3053 ms 42388 KB Output is correct
13 Correct 2055 ms 39260 KB Output is correct
14 Execution timed out 5061 ms 36468 KB Time limit exceeded
15 Halted 0 ms 0 KB -