Submission #636020

#	Time	Username	Problem	Language	Result	Execution time	Memory
636020		pakhomovee	Lampice (COCI19_lampice)	C++17	0 / 110	407 ms	524288 KiB

lampice

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <numeric>
#include <deque>

using namespace std;

const int sigma = 27;

struct aho {
    int sz;
    vector<int> link;
    vector<int> len;
    vector<int> p, c;
    vector<vector<int>> go;
    vector<vector<int>> to;
    int freeId = 1;

    void reset(int maxc) {
        go.resize(maxc);
        to.resize(maxc);
        for (int i = 0; i < maxc; ++i) {
            go[i].assign(sigma, -1);
        }
        for (int i = 0; i < maxc; ++i) {
            to[i].assign(sigma, -1);
        }
        link.assign(maxc, -1);
        len.assign(maxc, 0);
        p.assign(maxc, 0);
        c.assign(maxc, 0);
        freeId = 1;
        link[0] = 0;
        sz = maxc;
    }

    void corasickReset() {
        for (int i = 0; i < freeId; ++i) {
            to[i].assign(sigma, -1);
        }
        link.assign(freeId, -1);
    }
    
    int createNode(int v, char chr) {
        len[freeId] = len[v] + 1;
        c[freeId] = chr;
        p[freeId] = v;
        for (int j = 0; j < sigma; ++j) {
            go[freeId][j] = -1;
        }
        link[freeId] = 0;
        return freeId++;
    }

    int extend(char c, int v) {
        if (go[v][c] != -1) return go[v][c];
        return go[v][c] = createNode(v, c);
    }
    
    int lnk(int v) {
        if (link[v] == -1) {
            if (v == 0 || p[v] == 0) link[v] = 0;
            else link[v] = t(lnk(p[v]), c[v]);
        }
        return link[v];
    }
    
    int t(int v, int c) {
        if (to[v][c] == -1) {
            if (go[v][c] != -1) {
                to[v][c] = go[v][c];
            } else if (!v) {
                to[v][c] = v;
            } else {
                to[v][c] = t(lnk(v), c);
            }
        }
        return to[v][c];
    }
};

int ans = 1;
const int maxn = 50000 + 10;
bool used[maxn];
int sz[maxn];
int treeSize = 0;
string s;

void dfs(int v, vector<vector<int>> &g, int p) {
    sz[v] = 1;
    for (int u : g[v]) {
        if (!used[u] && u != p) {
            dfs(u, g, v);
            sz[v] += sz[u];
        }
    }
}

int centroid(int v, vector<vector<int>> &g, int p) {
    for (int u : g[v]) {
        if (!used[u] && u != p && sz[u] > treeSize / 2) {
            return centroid(u, g, v);
        }
    }
    return v;
}

const int P = 29;
const int lg = 16;
const int mod = 1e9 + 7;
int PP[maxn];

vector<aho> bits(lg);
vector<bool> have(lg);

aho curr;
set<int> ids;

void addAll(aho &a, int v1, int v2) {
    for (int i = 0; i < sigma; ++i) {
        if (a.go[v1][i] != -1 && curr.go[v2][i] == -1) {
            curr.go[v2][i] = curr.createNode(v2, i);
        }
        if (a.go[v1][i] != -1) {
            addAll(a, a.go[v1][i], curr.go[v2][i]);
        }
    }
}

void rebuild() {
    for (int i = 0; i < lg; ++i) {
        if (!have[i]) {
            bits[i] = curr;
            have[i] = true;
            bits[i].corasickReset();
            return;
        }
        have[i] = false;
        addAll(bits[i], 0, 0);
    }
}

vector<int> go(char c, vector<int> last) {
    for (int i = 0; i < lg; ++i) {
        if (have[i]) {
            last[i] = bits[i].t(last[i], c);
        }
    }
    return last;
}

int getMaxLen(vector<int> &last) {
    int rs = 0;
    for (int i = 0; i < lg; ++i) {
        if (have[i]) {
            rs = max(rs, bits[i].len[last[i]]);
        }
    }
    return rs;
}

void dfs(int v, vector<vector<int>> &g, int p, int h, int hrev, vector<int> last, int len) {
    int x = -1;
    if (h == hrev) {
        ans = max(ans, len);
        ids.insert(len);
        x = len;
    }
    h = (h * 1ll * P + s[v]) % mod;
    hrev = (hrev + PP[len] * 1ll * s[v]) % mod;
    if (h == hrev) {
        ans = max(ans, len + 1);
    }
    last = go(s[v], last);
    for (int i = 0; i < lg; ++i) {
        if (have[i]) {
            int u = last[i];
            while (u) {
                if (ids.count(len + 1 - bits[i].len[u])) {
                    ans = max(ans, len + 1 + bits[i].len[u]);
                    break;
                }
                u = bits[i].lnk(u);
            }
        }
    }
    for (int u : g[v]) {
        if (!used[u] && u != p) {
            dfs(u, g, v, h, hrev, last, len + 1);
        }
    }
    ids.erase(x);
}

void dfs1(int v, vector<vector<int>> &g, int p, int last) {
    last = curr.extend(s[v], last);
    for (int u : g[v]) {
        if (!used[u] && u != p) {
            dfs1(u, g, v, last);
        }
    }
}

void build(int v, vector<vector<int>> &g) {
    dfs(v, g, -1);
    treeSize = sz[v];
    v = centroid(v, g, -1);
    dfs(v, g, -1);
    used[v] = 1;
    for (int i = 0; i < lg; ++i) {
        bits[i].reset(treeSize + 10);
    }
    have.assign(lg, false);
    vector<int> vs(lg, 0);
    for (int u : g[v]) {
        if (!used[u]) {
            dfs(u, g, v, s[v], s[v], go(s[v], vs), 1);
            curr.reset(sz[u] + 10);
            dfs1(u, g, v, 0);
            rebuild();
        }
    }
    reverse(g[v].begin(), g[v].end());
    for (int i = 0; i < lg; ++i) {
        bits[i].reset(treeSize + 10);
    }
    have.assign(lg, false);
    for (int u : g[v]) {
        if (!used[u]) {
            dfs(u, g, v, s[v], s[v], go(s[v], vs), 1);
            curr.reset(sz[u] + 10);
            dfs1(u, g, v, 0);
            rebuild();
        }
    }
    for (int u : g[v]) {
        if (!used[u]) {
            build(u, g);
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    PP[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        PP[i] = (PP[i - 1] * 1ll * P) % mod;
    }
    int n;
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        s[i] = s[i] - 'a' + 1;
    }
    vector<vector<int>> g(n);
    for (int i = 0; i + 1 < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build(0, g);
    cout << ans;
}

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