oj.uz

Submission #636022

# Submission time Handle Problem Language Result Execution time Memory
636022 2022-08-27T17:25:48 Z pakhomovee Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 290676 KB 
#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) {
        assert(freeId < sz);
        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 &curr, 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(curr, 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;
        aho nw;
        nw.reset(curr.sz + bits[i].sz);
        addAll(nw, bits[i], 0, 0);
        addAll(nw, curr, 0, 0);
        curr = nw;
    }
}

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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2388 KB Output is correct
2 Correct 33 ms 4820 KB Output is correct
3 Correct 76 ms 9148 KB Output is correct
4 Correct 109 ms 12952 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2964 ms 251112 KB Output is correct
2 Correct 3093 ms 258660 KB Output is correct
3 Correct 3150 ms 264432 KB Output is correct
4 Correct 3433 ms 277428 KB Output is correct
5 Correct 3393 ms 290432 KB Output is correct
6 Correct 3713 ms 290676 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3627 ms 275784 KB Output is correct
2 Correct 3363 ms 261640 KB Output is correct
3 Correct 3375 ms 261216 KB Output is correct
4 Execution timed out 5062 ms 271684 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2388 KB Output is correct
2 Correct 33 ms 4820 KB Output is correct
3 Correct 76 ms 9148 KB Output is correct
4 Correct 109 ms 12952 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2964 ms 251112 KB Output is correct
9 Correct 3093 ms 258660 KB Output is correct
10 Correct 3150 ms 264432 KB Output is correct
11 Correct 3433 ms 277428 KB Output is correct
12 Correct 3393 ms 290432 KB Output is correct
13 Correct 3713 ms 290676 KB Output is correct
14 Correct 3627 ms 275784 KB Output is correct
15 Correct 3363 ms 261640 KB Output is correct
16 Correct 3375 ms 261216 KB Output is correct
17 Execution timed out 5062 ms 271684 KB Time limit exceeded
18 Halted 0 ms 0 KB -