oj.uz

답안 #764794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764794 2023-06-24T04:37:11 Z 1075508020060209tc Lampice (COCI19_lampice) C++14
42 / 110
 5000 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;
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{
    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]<=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: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:89: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]
   89 | for(int i=0;i<e[ctr].size();i++){
      |             ~^~~~~~~~~~~~~~
lampice.cpp:109: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]
  109 | for(int i=0;i<e[ctr].size();i++){
      |             ~^~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:166:5: warning: unused variable 'v' [-Wunused-variable]
  166 | int v;/*
      |     ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 21120 KB Output is correct
2 Correct 203 ms 21276 KB Output is correct
3 Correct 236 ms 21608 KB Output is correct
4 Correct 251 ms 21528 KB Output is correct
5 Correct 192 ms 21024 KB Output is correct
6 Correct 192 ms 21032 KB Output is correct
7 Correct 192 ms 20972 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2132 ms 42968 KB Output is correct
2 Correct 2416 ms 43528 KB Output is correct
3 Correct 2413 ms 44088 KB Output is correct
4 Correct 2504 ms 45200 KB Output is correct
5 Correct 2916 ms 46332 KB Output is correct
6 Correct 2164 ms 44760 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 21120 KB Output is correct
2 Correct 203 ms 21276 KB Output is correct
3 Correct 236 ms 21608 KB Output is correct
4 Correct 251 ms 21528 KB Output is correct
5 Correct 192 ms 21024 KB Output is correct
6 Correct 192 ms 21032 KB Output is correct
7 Correct 192 ms 20972 KB Output is correct
8 Correct 2132 ms 42968 KB Output is correct
9 Correct 2416 ms 43528 KB Output is correct
10 Correct 2413 ms 44088 KB Output is correct
11 Correct 2504 ms 45200 KB Output is correct
12 Correct 2916 ms 46332 KB Output is correct
13 Correct 2164 ms 44760 KB Output is correct
14 Execution timed out 5071 ms 36688 KB Time limit exceeded
15 Halted 0 ms 0 KB -