oj.uz

Submission #923023

# Submission time Handle Problem Language Result Execution time Memory
923023 2024-02-06T12:47:16 Z ttamx Lampice (COCI19_lampice) C++14
73 / 110
 3089 ms 38048 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
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;
gp_hash_table<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 7 ms 20824 KB Output is correct
2 Correct 12 ms 21084 KB Output is correct
3 Correct 34 ms 21472 KB Output is correct
4 Correct 35 ms 21084 KB Output is correct
5 Correct 4 ms 18776 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1377 ms 37424 KB Output is correct
2 Correct 1287 ms 37284 KB Output is correct
3 Correct 825 ms 37644 KB Output is correct
4 Correct 700 ms 37860 KB Output is correct
5 Correct 1825 ms 38048 KB Output is correct
6 Correct 114 ms 30408 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2209 ms 35812 KB Output is correct
2 Correct 2954 ms 35576 KB Output is correct
3 Correct 2295 ms 36512 KB Output is correct
4 Correct 2104 ms 30752 KB Output is correct
5 Correct 1873 ms 35904 KB Output is correct
6 Correct 1773 ms 37820 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20824 KB Output is correct
2 Correct 12 ms 21084 KB Output is correct
3 Correct 34 ms 21472 KB Output is correct
4 Correct 35 ms 21084 KB Output is correct
5 Correct 4 ms 18776 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 1377 ms 37424 KB Output is correct
9 Correct 1287 ms 37284 KB Output is correct
10 Correct 825 ms 37644 KB Output is correct
11 Correct 700 ms 37860 KB Output is correct
12 Correct 1825 ms 38048 KB Output is correct
13 Correct 114 ms 30408 KB Output is correct
14 Correct 2209 ms 35812 KB Output is correct
15 Correct 2954 ms 35576 KB Output is correct
16 Correct 2295 ms 36512 KB Output is correct
17 Correct 2104 ms 30752 KB Output is correct
18 Correct 1873 ms 35904 KB Output is correct
19 Correct 1773 ms 37820 KB Output is correct
20 Correct 1497 ms 29592 KB Output is correct
21 Correct 1849 ms 35572 KB Output is correct
22 Correct 2659 ms 35560 KB Output is correct
23 Correct 484 ms 18056 KB Output is correct
24 Correct 2041 ms 21592 KB Output is correct
25 Correct 1989 ms 21304 KB Output is correct
26 Correct 2660 ms 31068 KB Output is correct
27 Correct 2643 ms 30208 KB Output is correct
28 Correct 1320 ms 18000 KB Output is correct
29 Correct 1475 ms 18268 KB Output is correct
30 Incorrect 3089 ms 22064 KB Output isn't correct
31 Halted 0 ms 0 KB -