oj.uz

Submission #923022

# Submission time Handle Problem Language Result Execution time Memory
923022 2024-02-06T12:46:06 Z ttamx Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 32596 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int N=5e5+5;
const ull BASE=rng();
const ull BASE2=rng();
const ull BASE3=rng();
 
int n;
string s;
ull a[N];
vector<int> adj[N];
ull hsh[26],pw[N],pw2[N];
int sz[N];
bool used[N];
int len;
map<ull,bool> mp;

ull calc(ull x,ull y,ull z){
    return (x*BASE3+y)*BASE3+z;
}
 
void init(){
    for(int i=1;i<=n;i++)used[i]=false;
}
 
int get_sz(int u,int p=0){
    sz[u]=1;
    for(auto v:adj[u])if(v!=p&&!used[v])sz[u]+=get_sz(v,u);
    return sz[u];
}
 
int centroid(int u,int cnt,int p=0){
    for(auto v:adj[u])if(v!=p&&!used[v]&&sz[v]>cnt/2)return centroid(v,cnt,u);
    return u;
}
 
bool dfs1(int u,int p,ull cur,ull rev,ull cur2,ull rev2,int sz){
    if(sz>len)return false;
    if(mp[calc(rev*pw[len-sz]-cur,rev2*pw2[len-sz]-cur2,len-sz)])return true;
    for(auto v:adj[u])if(v!=p&&!used[v]){
        if(dfs1(v,u,cur*BASE+a[v],rev+a[v]*pw[sz],cur2*BASE2+a[v],rev2+a[v]*pw2[sz],sz+1)){
            return true;
        }
    }
    return false;
}
 
void dfs2(int u,int p,ull cur,ull rev,ull cur2,ull rev2,int sz){
    if(sz>len)return;
    mp[calc(rev*pw[len-sz]-cur,rev2*pw2[len-sz]-cur2,sz)]=true;
    for(auto v:adj[u])if(v!=p&&!used[v]){
        dfs2(v,u,cur*BASE+a[v],rev+a[v]*pw[sz],cur2*BASE2+a[v],rev2+a[v]*pw2[sz],sz+1);
    }
}

bool dfs3(int u,int p,ull cur,ull rev,ull cur2,ull rev2,int sz){
    if(sz>len)return false;
    if(sz==len&&cur==rev&&cur2==rev2)return true;
    for(auto v:adj[u])if(v!=p&&!used[v]){
        if(dfs3(v,u,cur*BASE+a[v],rev+a[v]*pw[sz],cur2*BASE2+a[v],rev2+a[v]*pw2[sz],sz+1)){
            return true;
        }
    }
    return false;
}
 
bool decom(int u){
    u=centroid(u,get_sz(u));
    used[u]=true;
    if(dfs3(u,u,a[u],a[u],a[u],a[u],1))return true;
    mp.clear();
    for(auto v:adj[u])if(!used[v]){
        if(dfs1(v,u,a[v],a[v],a[v],a[v],1))return true;
        dfs2(v,u,a[u]*BASE+a[v],a[v]*BASE+a[u],a[u]*BASE2+a[v],a[v]*BASE2+a[u],2);
    }
    for(auto v:adj[u])if(!used[v]&&decom(v))return true;
    return false;
}

int solve1(){
    int l=0,r=(n-1)/2;
    while(l<r){
        int m=(l+r+1)/2;
        len=m*2+1;
        init();
        if(decom(1))l=m;
        else r=m-1;
    }
    return l*2+1;
}
 
int solve2(){
    int l=0,r=n/2;
    while(l<r){
        int m=(l+r+1)/2;
        len=m*2;
        init();
        if(decom(1))l=m;
        else r=m-1;
    }
    return l*2;
}
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    for(int i=0;i<26;i++)hsh[i]=rng();
    cin >> n >> s;
    pw[0]=pw2[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*BASE;
    for(int i=1;i<=n;i++)pw2[i]=pw2[i-1]*BASE2;
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'a'+1;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    cout << max(solve1(),solve2());
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20828 KB Output is correct
2 Correct 14 ms 21064 KB Output is correct
3 Correct 46 ms 21336 KB Output is correct
4 Correct 54 ms 21328 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20924 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2663 ms 30884 KB Output is correct
2 Correct 3230 ms 31024 KB Output is correct
3 Correct 2299 ms 31568 KB Output is correct
4 Correct 1985 ms 31988 KB Output is correct
5 Correct 4450 ms 32596 KB Output is correct
6 Correct 500 ms 29284 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4000 ms 29980 KB Output is correct
2 Execution timed out 5019 ms 29520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20828 KB Output is correct
2 Correct 14 ms 21064 KB Output is correct
3 Correct 46 ms 21336 KB Output is correct
4 Correct 54 ms 21328 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20924 KB Output is correct
8 Correct 2663 ms 30884 KB Output is correct
9 Correct 3230 ms 31024 KB Output is correct
10 Correct 2299 ms 31568 KB Output is correct
11 Correct 1985 ms 31988 KB Output is correct
12 Correct 4450 ms 32596 KB Output is correct
13 Correct 500 ms 29284 KB Output is correct
14 Correct 4000 ms 29980 KB Output is correct
15 Execution timed out 5019 ms 29520 KB Time limit exceeded
16 Halted 0 ms 0 KB -