Submission #1156680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156680		knhatdev	Lampice (COCI19_lampice)	C++17	0 / 110	5094 ms	36696 KiB

lampice

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N = 5e4 + 5, base = 31, mod = 1e9 + 7;
int n, sz[N], h[N], ans;
int up[N], down[N], H, mx_h;
int Pow[N], a[N];
bool is_centroid[N];
string s;
vector<int> g[N];
map<int, bool> d[N];

void dfs(int u, int par = -1){
    sz[u] = 1;
    for(int v : g[u]){
        if(v == par || is_centroid[v]) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int tree_sz, int par = -1){
    for(int v : g[u]){
        if(v != par && !is_centroid[v] && sz[v] > tree_sz/2)
            return find_centroid(v, tree_sz, u);
    }
    return u;
}  

bool get(int u, int par = 0){
    h[u] = h[par] + 1;
    mx_h = max(mx_h, h[u]);
    if(h[u] > H) return 0;
    down[h[u]] = (down[h[u] - 1]*base + a[u]) % mod;
    up[h[u]] = (a[u] * Pow[h[u] - 1] + up[h[u] - 1]) % mod;
    int tmp = (up[h[u]] * Pow[H - h[u]] - down[h[u]] + mod) % mod;
    if(up[h[u]] == down[h[u]] && h[u] == H) return 1;
    if(d[H - h[u]][tmp]) return 1;
    for(int v : g[u]){
        if(v != par && !is_centroid[v])
            if(get(v, u)) return 1;
    }
    return 0;
}


void update(int u, int par = 0){
    h[u] = h[par] + 1;
    mx_h = max(mx_h, h[u]);
    if(h[u] > H) return;
    down[h[u]] = (down[h[u] - 1]*base + a[u]) % mod;
    up[h[u]] = (a[u] * Pow[h[u] - 1] + up[h[u] - 1]) % mod;
    int tmp = (up[h[u]] * Pow[H - h[u]] - down[h[u]] + mod) % mod;
    d[h[u]][tmp] = 1;
    for(int v : g[u])  
        if(v != par && !is_centroid[v])
            update(v, u);
}

bool build_centroid(int u){
    dfs(u);
    int centroid = find_centroid(u, sz[u]);
    is_centroid[centroid] = 1;
    for(int v : g[centroid]){
        if(!is_centroid[v]){
            h[centroid] = 1;
            up[1] = down[1] = a[centroid];
            if(get(v, centroid)) return 1;
            h[centroid] = up[0] = down[0] = 0;
            update(v);
        }
    }
    for(int i = 0; i <= mx_h; i++)
        d[i].clear();
    for(int v : g[centroid])
        if(!is_centroid[v] && build_centroid(v))
            return 1;

    return 0;
}

bool check(int x){
    if(x > n) return 0;
    for(int i = 1; i <= n; i++){
        d[i].clear();
        is_centroid[i] = 0;
    }
    H = x;
    return build_centroid(1);
}
void solve(){
    int l = 1, r = n/2;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid << 1)){
            l = mid + 1;
            ans = mid << 1;
        } else {
            r = mid - 1;
        }
    }
    l = 1, r = n/2;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid << 1 | 1)){
            l = mid + 1;
            ans = max(ans, mid << 1 | 1);
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    s = ' ' + s;
    for(int i = 1; i <= n; i++)
        a[i] = s[i] - 'a' + 1;
    // for(int i = 1; i <= n; i++)
    //     cout << a[i] << ' ';
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    Pow[0] = 1;
    for(int i = 1; i <= n; i++){
        Pow[i] = (Pow[i - 1] * base) % mod;
    }
    solve();
}

Compilation message (stderr)

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

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37