oj.uz

Submission #1023325

# Submission time Handle Problem Language Result Execution time Memory
1023325 2024-07-14T15:43:13 Z doducanh Lampice (COCI19_lampice) C++14
110 / 110
 2109 ms 11792 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e4+7;
const int mod=1e9+7;
const int base=9973;
int lo[maxn];
vector<int>adj[maxn];
int subsz[maxn];
bool removed[maxn];
int dis[maxn];
int color[maxn];
int curdn[maxn];
int down[maxn];
bool pal[maxn];
int up[maxn];
bool bb=0;
vector<int>toadd_l,toadd_s;
set<int>hashl,hashs;
string s;
int n;
int curlen;
int get(int l,int r,int x,int y){
    return (y-(lo[(r-l)]*x)%mod+2*mod)%mod;
}
int get_subsize(int u,int par){
    subsz[u]=1;
    for(int v:adj[u]){
        if(removed[v]||v==par)continue;
        get_subsize(v,u);
        subsz[u]+=subsz[v];
    }
    return subsz[u];
}
int find_cen(int u,int par,int treesize){
    for(int v:adj[u]){
        if(removed[v]||v==par)continue;
        if((subsz[v]*2)>treesize)return find_cen(v,u,treesize);
    }
    return u;
}
void dfs(int u,int par){
    if(bb)return;
    dis[u]=dis[par]+1;
    if(dis[u]>curlen)return;
    curdn[dis[u]]=u;
    down[u]=(down[par]*base%mod+color[u])%mod;
    up[u]=(up[par]+color[u]*lo[dis[u]]%mod)%mod;
    pal[u]=(down[u]==up[u]);
    if(dis[u]==curlen){
        bb=pal[u];
    }
    else if(dis[u]>curlen/2){
        int diff=dis[u]*2-curlen;
        int c=curdn[diff];
        if(pal[c]){
            int hn=get(dis[c]-1,dis[u],down[curdn[diff-1]],down[u]);
            if(hashs.count(hn))bb=1;
            toadd_l.push_back(hn);
        }
    }
    else{
        if(hashl.count(down[u]))bb=1;
        toadd_s.push_back(down[u]);
    }
    if(dis[u]*2==curlen){
        if(hashs.count(down[u]))bb=1;
    }

    for(int v:adj[u]){
        if(v==par||removed[u])continue;
        dfs(v,u);
    }

}
void centroid_decomp(int u=1){
    if(bb)return;
    int cen=find_cen(u,0,get_subsize(u,0));
    removed[cen]=1;
    curdn[0]=cen;
    dis[cen]=0;
    down[cen]=color[cen];
    up[cen]=color[cen];
    for(int v:adj[cen]){
        if(removed[v])continue;
        dfs(v,cen);
        for(int x:toadd_l)hashl.insert(x);
        for(int x:toadd_s)hashs.insert(x);
        toadd_l.clear();
        toadd_s.clear();
    }
    hashl.clear();
    hashs.clear();
    for(int v:adj[cen]){
        if(removed[v]==0){
            centroid_decomp(v);
        }
    }

}
bool check(int length){
    if(length==1)return true;
    curlen=length-1;
    for(int i=1;i<=n;i++)removed[i]=0;
    bb=0;
    centroid_decomp();
    return bb;
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    lo[0]=1;
    for(int i=1;i<=n;i++)lo[i]=(lo[i-1]*base)%mod;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++)color[i]=s[i]-'a'+1;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    //odd len
    int l=0,r=n/2-((n%2)==0);
    int res=0;
    while(l<=r){
        int m=(l+r)/2;
        if(check(2*m+1)){
            res=max(res,2*m+1);
            l=m+1;
        }
        else r=m-1;
    }

    l=(res)/2+1,r=n/2;
    while(l<=r){
        int m=(l+r)/2;
        if(check(2*m)){
            res=max(res,2*m);
            l=m+1;
        }
        else r=m-1;
    }
    cout<<res;
}

Compilation message

lampice.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 5 ms 3764 KB Output is correct
3 Correct 20 ms 3868 KB Output is correct
4 Correct 21 ms 3880 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 10100 KB Output is correct
2 Correct 1303 ms 10544 KB Output is correct
3 Correct 787 ms 11716 KB Output is correct
4 Correct 850 ms 11792 KB Output is correct
5 Correct 1449 ms 11724 KB Output is correct
6 Correct 138 ms 11224 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 9744 KB Output is correct
2 Correct 2109 ms 9560 KB Output is correct
3 Correct 2029 ms 9692 KB Output is correct
4 Correct 1815 ms 8932 KB Output is correct
5 Correct 1907 ms 9040 KB Output is correct
6 Correct 1686 ms 8692 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 5 ms 3764 KB Output is correct
3 Correct 20 ms 3868 KB Output is correct
4 Correct 21 ms 3880 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 905 ms 10100 KB Output is correct
9 Correct 1303 ms 10544 KB Output is correct
10 Correct 787 ms 11716 KB Output is correct
11 Correct 850 ms 11792 KB Output is correct
12 Correct 1449 ms 11724 KB Output is correct
13 Correct 138 ms 11224 KB Output is correct
14 Correct 1761 ms 9744 KB Output is correct
15 Correct 2109 ms 9560 KB Output is correct
16 Correct 2029 ms 9692 KB Output is correct
17 Correct 1815 ms 8932 KB Output is correct
18 Correct 1907 ms 9040 KB Output is correct
19 Correct 1686 ms 8692 KB Output is correct
20 Correct 980 ms 7752 KB Output is correct
21 Correct 1187 ms 8056 KB Output is correct
22 Correct 1919 ms 8864 KB Output is correct
23 Correct 414 ms 7184 KB Output is correct
24 Correct 1218 ms 8140 KB Output is correct
25 Correct 1461 ms 7904 KB Output is correct
26 Correct 1920 ms 9676 KB Output is correct
27 Correct 1683 ms 9176 KB Output is correct
28 Correct 1094 ms 7260 KB Output is correct
29 Correct 1114 ms 7252 KB Output is correct
30 Correct 1642 ms 8672 KB Output is correct
31 Correct 1380 ms 7712 KB Output is correct
32 Correct 1418 ms 9524 KB Output is correct
33 Correct 905 ms 8788 KB Output is correct