Submission #1267434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267434		Bui_Quoc_Cuong	Lampice (COCI19_lampice)	C++20	110 / 110	2128 ms	39172 KiB

lampice

#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int maxn = 50005;
const int base = 311, mod = 1e9 + 7;

int n;
string s;
vector <int> g[maxn];
int is_cen[maxn], sz[maxn];
int pw[maxn];

int add(int x, int y){
    return (x + y) % mod;
}

int mul(int x, int y){
    return 1LL * x * y % mod;
}

int sub(int x, int y){
    return (x - y + mod) % mod;
}

void dfs_sz(int u, int p) {
    sz[u] = 1;
    for(int &v : g[u]) if(!is_cen[v] && v != p){
        dfs_sz(v, u);
        sz[u]+= sz[v];
    }
}

int findcen(int u, int p, int big){
    for(int &v : g[u]) if(!is_cen[v] && v != p){
        if(sz[v] > big / 2) return findcen(v, u, big);
    }
    return u;
}

int ans = 1;
int hsh[maxn], rev_hsh[maxn], hei[maxn], par[maxn];
unordered_map <int, bool> mp[50005];
int len = 0, ok = 0;
int h[50005], ma = 0;

int getAns(int u, int p, int type){
    h[u] = h[p] + 1;
    ma = max(ma, h[u]);

    if(h[u] > len) return 0;
    hsh[u] = add(mul(hsh[p], base), s[u] - 'a' + 1);
    rev_hsh[u] = add(mul(s[u] - 'a' + 1, pw[h[u] - 1]), rev_hsh[p]);

    if(type == 0){
        if(hsh[u] == rev_hsh[u] && h[u] + 1 >= len && (len % 2 == h[u] % 2)) return 1;
        int curHash = (1LL * rev_hsh[u] * pw[len - h[u]] - hsh[u] + mod) % mod;
        if(mp[len - h[u]].find(curHash) != mp[len - h[u]].end()) return 1;
    } else{
        int curHash = (1LL * rev_hsh[u] * pw[len - h[u]] - hsh[u] + mod) % mod;
        mp[h[u]][curHash] = 1;
    }   
    for(int &v : g[u]) if(!is_cen[v] && v != p){
        if(getAns(v, u, type)) return 1;
    }
    return false;
}

int buildcen(int u){
    dfs_sz(u, - 1);
    int centroid = findcen(u, - 1, sz[u]);
    is_cen[centroid] = true;
    ma = 0;

    for(int &v : g[centroid]){
        if(is_cen[v]) continue;
        h[centroid] = 1;
        hsh[centroid] = rev_hsh[centroid] = (s[centroid] - 'a' + 1);
        if(getAns(v, centroid, 0)) return 1;
        h[centroid] = 0;
        hsh[centroid] = rev_hsh[centroid] = 0;
        getAns(v, centroid, 1);
    }

    for(int i = 0; i <= ma; i++) mp[i].clear();

    for(int &v : g[centroid]){
        if(!is_cen[v] && buildcen(v)) return true;
    }
    return false;
}

bool check(){
    for(int i = 1; i <= n; i++) is_cen[i] = sz[i] = 0;
    return buildcen(1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  //  freopen("lampice.inp", "r", stdin);
  //  freopen("lampice.out", "w", stdout);

    cin >> n >> s; s = "*" + s;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }

    pw[0] = 1;
    for(int i = 1; i <= n; i++){
        pw[i] = 1LL * pw[i - 1] * base % mod;
    }

    int l = 1, r = n / 2;
    
    while(l <= r){
        int mid = (l + r) >> 1;
        len = 2 * mid;
        if(check()) ans = max(ans, len), l = mid + 1;
        else r = mid - 1;
    }
    
    l = 0, r = (n - 1) / 2;
    while(l <= r){
        int mid = (l + r) >> 1;
        len = 2 * mid + 1;
        if(check()) ans = max(ans, len), l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;

    return 0;
}

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