Submission #211746

#	Time	Username	Problem	Language	Result	Execution time	Memory
211746		VEGAnn	Lampice (COCI19_lampice)	C++14	110 / 110	3224 ms	19448 KiB

lampice

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 50100;
const int PW = 233;
const int PO = 20;
const int md = 998244353;
__gnu_pbds::gp_hash_table<int, bool> mem[N];
vector<int> vc, g[N];
string s;
int ans = 0, kol, siz[N], mem_up[N], mem_down[N], po[N], inv[N], n, hsh[N][2], shsh[N], ANS[N][2];
bool mrk[N];

int mult(int x, int y) { return (1ll * x * y) % md; }

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int sub(int x, int y){
    x -= y;
    if (x < 0)
        x += md;
    return x;
}

int binpow(int x, int po){
    int res = 1;
    while (po > 0){
        if (po & 1)
            res = mult(res, x);

        x = mult(x, x);
        po >>= 1;
    }
    return res;
}

void build_sz(int v, int p){
    siz[v] = 1;
    for (int u : g[v]){
        if (u == p || mrk[u]) continue;
        build_sz(u, v);
        siz[v] += siz[u];
    }
}

int search(int v, int p, int SZ){
    for (int u : g[v])
        if (u != p && !mrk[u] && siz[u] > SZ / 2)
            return search(u, v, SZ);
    return v;
}

void calc_h(int v, int p, int h1, int h2, int shs, int ht){
    hsh[v][0] = h1;
    hsh[v][1] = h2;
    shsh[v] = shs;

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        int ch = s[u] - 'a' + 1;
        calc_h(u, v, sum(h1, mult(po[ht], ch)), sum(h2, mult(po[ht + 1], ch)), sum(ch, mult(PW, shs)), ht + 1);
    }
}

void change(int v, int p, int ht){
    mem[ht][hsh[v][0]] = 1;

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        change(u, v, ht + 1);
    }
}

void dfs(int v, int p, int ht, int len){
    if (ht + 1 > len) return;

    int hs = hsh[v][1];
    int shs = shsh[v];

    mem_up[ht] = shs;
    mem_down[ht] = hs;

    int c_len = len - (ht + 1);
    int c_ht = ht - c_len;

    if (c_ht >= 0){
        if (mem_up[c_ht] == mem_down[c_ht]) {
            int chs = sub(hs, mem_down[c_ht]);
            chs = mult(chs, inv[c_ht + 1]);

            if (mem[c_len].find(chs) != mem[c_len].end())
                kol++;
        }
    }

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        dfs(u, v, ht + 1, len);
    }
}

void check(int v, int p, int st){
    int l = 0, r = siz[v];

    while (l < r){
        int md = (l + r + 1) >> 1;
        int len = md + md + st;
        
        if (ANS[v][st] >= len){
            l = md;
            continue;
        }
        
        kol = 0;

        mem_up[0] = mem_down[0] = s[v] - 'a' + 1;

        for (int i = 1; i < siz[v]; i++)
            mem[i].clear();

        for (int u : g[v]){
            if (u == p || mrk[u]) continue;
            dfs(u, v, 1, len);
            change(u, v, 1);
        }

        for (int i = 1; i < siz[v]; i++)
            mem[i].clear();

        for (int it = sz(g[v]) - 1; it >= 0; it--){
            int u = g[v][it];
            if (u == p || mrk[u]) continue;
            dfs(u, v, 1, len);
            change(u, v, 1);
        }

        if (kol > 0)
            l = md;
        else r = md - 1;
    }

    ANS[v][st] = max(ANS[v][st], l + l + st);
    ans = max(ans, l + l + st);
}

void build_cd(int v, int p){
    build_sz(v, p);
    v = search(v, p, siz[v]);
    build_sz(v, p);

    mrk[v] = 1;
    for (int u : g[v])
        if (u != p && !mrk[u]) 
            build_cd(u, v);

    calc_h(v, p, 0, s[v] - 'a' + 1, s[v] - 'a' + 1, 0);
            
    check(v, p, 0);
    check(v, p, 1);

    if (p >= 0){
        ANS[p][0] = max(ANS[v][0], ANS[p][0]);
        ANS[p][1] = max(ANS[v][1], ANS[p][1]);
    }
    
    mrk[v] = 0;
}

int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("217.in","r",stdin);

    cin >> n >> s;

    po[0] = 1;
    for (int i = 1; i <= n; i++) {
        po[i] = mult(po[i - 1], PW);
        inv[i] = binpow(po[i], md - 2);
    }

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].PB(y);
        g[y].PB(x);
    }

    mem[0][0] = 1;
    build_cd(0, -1);

    cout << ans;

    return 0;
}

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