oj.uz

Submission #923019

# Submission time Handle Problem Language Result Execution time Memory
923019 2024-02-06T12:40:09 Z ttamx Lampice (COCI19_lampice) C++14
42 / 110
 4697 ms 28308 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
using ull = unsigned long long;
using pu=pair<ull,int>;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int N=5e5+5;
const ull BASE=rng();
 
int n;
string s;
ull a[N];
vector<int> adj[N];
ull hsh[26],pw[N];
int sz[N];
bool used[N];
int len;
map<pu,bool> mp;
 
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,int sz){
    if(sz>len)return false;
    if(mp[pu(rev*pw[len-sz]-cur,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],sz+1)){
            return true;
        }
    }
    return false;
}
 
void dfs2(int u,int p,ull cur,ull rev,int sz){
    if(sz>len)return;
    mp[pu(rev*pw[len-sz]-cur,sz)]=true;
    for(auto v:adj[u])if(v!=p&&!used[v]){
        dfs2(v,u,cur*BASE+a[v],rev+a[v]*pw[sz],sz+1);
    }
}

bool dfs3(int u,int p,ull cur,ull rev,int sz){
    if(sz>len)return false;
    if(sz==len&&cur==rev)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],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],1))return true;
    mp.clear();
    for(auto v:adj[u])if(!used[v]){
        if(dfs1(v,u,a[v],a[v],1))return true;
        dfs2(v,u,a[u]*BASE+a[v],a[v]*BASE+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]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*BASE;
    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 7 ms 16728 KB Output is correct
2 Correct 13 ms 16732 KB Output is correct
3 Correct 47 ms 17088 KB Output is correct
4 Correct 50 ms 16988 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2706 ms 26780 KB Output is correct
2 Correct 3274 ms 26920 KB Output is correct
3 Correct 2354 ms 27288 KB Output is correct
4 Correct 3077 ms 27792 KB Output is correct
5 Correct 4697 ms 28308 KB Output is correct
6 Correct 549 ms 25856 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4135 ms 25880 KB Output is correct
2 Incorrect 4038 ms 25668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 13 ms 16732 KB Output is correct
3 Correct 47 ms 17088 KB Output is correct
4 Correct 50 ms 16988 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 2706 ms 26780 KB Output is correct
9 Correct 3274 ms 26920 KB Output is correct
10 Correct 2354 ms 27288 KB Output is correct
11 Correct 3077 ms 27792 KB Output is correct
12 Correct 4697 ms 28308 KB Output is correct
13 Correct 549 ms 25856 KB Output is correct
14 Correct 4135 ms 25880 KB Output is correct
15 Incorrect 4038 ms 25668 KB Output isn't correct
16 Halted 0 ms 0 KB -