Submission #1097912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097912		f0rizen	Lampice (COCI19_lampice)	C++17	0 / 110	5040 ms	12968 KiB

lampice

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct BinaryJumps {
    static const int lg = 16;

    vector<int> d;
    vector<vector<int>> up;

    BinaryJumps() {}
    BinaryJumps(int n) {
        d.resize(n);
        up.resize(lg, vector<int>(n, -1));
    }

    void add_leaf(int v, int p) {
        d[v] = d[p] + 1;
        up[0][v] = p;
        for (int i = 1; i < lg; ++i) {
            if (up[i - 1][v] != -1) {
                up[i][v] = up[i - 1][up[i - 1][v]];
            }
        }
    }

    void remove(int v) {
        d[v] = 0;
        for (int i = 0; i < lg; ++i) {
            up[i][v] = -1;
        }
    }

    int la(int v, int k) {
        for (int i = lg - 1; i >= 0; --i) {
            if (k >= (1 << i)) {
                k -= (1 << i);
                v = up[i][v];
            }
        }
        return v;
    }
};

const int P = 227, mod = 1e9 + 9;

int mul(int a, int b) {
    return (a * 1ll * b) % mod;
}

int sub(int a, int b) {
    return ((a - b) % mod + mod) % mod;
}

vector<int> pw;

vector<int> a;
vector<vector<int>> g;
BinaryJumps tr;
vector<bool> used;
vector<int> sz;
vector<vector<int>> dp, rdp;
unordered_set<int> st;

void dfs_sz(int v, int p = -1) {
    sz[v] = 1;
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            tr.add_leaf(u, v);
            dfs_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

void dfs_dp(int v, int p = -1, int d = 0) {
    dp[0][v] = (mul(dp[0][p], P) + a[v]) % mod;
    rdp[0][v] = (mul(a[v], pw[d - 1]) + rdp[0][p]) % mod;
    dp[1][v] = (mul(dp[1][p], P) + a[v]) % mod;
    rdp[1][v] = (mul(a[v], pw[d]) + rdp[1][p]) % mod;
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            dfs_dp(u, v, d + 1);
        }
    }
}

bool dfs_ans(int len, int v, int p = -1, int d = 0) {
    if (d + 1 == len && dp[1][v] == rdp[1][v]) {
        return true;
    }
    if (len - d - 1 > 0) {
        if (2 * d + 2 - len > 0) {
            int u = tr.la(v, len - d - 1);
            if (dp[1][u] == rdp[1][u]) {
                int h = sub(dp[1][v], mul(pw[len - d - 1], dp[1][u]));
                if (st.find(h) != st.end()) {
                    return true;
                }
            }
        } else if (2 * d + 2 - len == 0) {
            int h = rdp[1][v];
            if (st.find(h) != st.end()) {
                return true;
            }
        }
    }
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            if (dfs_ans(len, u, v, d + 1)) {
                return true;
            }
        }
    }
    return false;
}

void dfs_insert(int v, int p = -1) {
    st.insert(dp[0][v]);
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            dfs_insert(u, v);
        }
    }
}

void dfs_clear(int v, int p = -1) {
    dp[0][v] = 0;
    rdp[0][v] = 0;
    dp[1][v] = 0;
    rdp[1][v] = 0;
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            dfs_clear(u, v);
            tr.remove(u);
        }
    }
}

int centroid(int v, int p, int n) {
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            if (sz[u] * 2 > n) {
                return centroid(u, v, n);
            }
        }
    }
    return v;
}

bool check(int v, int len) {
    dfs_sz(v);
    if (len == 1) {
        return true;
    }
    dp[1][v] = a[v];
    rdp[1][v] = a[v];
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs_dp(u, v, 1);
        }
    }
    for (auto u : g[v]) {
        if (!used[u]) {
            if (dfs_ans(len, u, v, 1)) {
                return true;
            }
            dfs_insert(u, v);
        }
    }
    st.clear();
    for (int i = (int) g[v].size() - 1; i >= 0; --i) {
        int u = g[v][i];
        if (!used[u]) {
            if (dfs_ans(len, u, v, 1)) {
                return true;
            }
            dfs_insert(u, v);
        }
    }
    st.clear();
    dfs_clear(v);
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            if (check(centroid(u, v, sz[u]), len)) {
                return true;
            }
        }
    }
    return false;
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n;
    cin >> n;
    pw.resize(n);
    pw[0] = 1;
    for (int i = 1; i < n; ++i) {
        pw[i] = mul(pw[i - 1], P);
    }
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        a[i] = c - 'a' + 1;
    }
    g.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    tr = BinaryJumps(n);
    used.resize(n);
    sz.resize(n);
    dp.resize(2, vector<int>(n));
    rdp.resize(2, vector<int>(n));
    dfs_sz(0);
    int ans = 0;
    {
        int l = 0, r = n / 2 + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (2 * mid > n) {
                r = mid;
                continue;
            }
            fill(used.begin(), used.end(), 0);
            fill(sz.begin(), sz.end(), 0);
            dfs_sz(0);
            if (check(centroid(0, -1, sz[0]), 2 * mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ans = max(ans, 2 * l);
    }
    {
        int l = 0, r = n / 2 + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (2 * mid + 1 > n) {
                r = mid;
                continue;
            }
            fill(used.begin(), used.end(), 0);
            fill(sz.begin(), sz.end(), 0);
            dfs_sz(0);
            if (check(centroid(0, -1, sz[0]), 2 * mid + 1)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ans = max(ans, 2 * l + 1);
    }
    cout << ans << "\n";
    return 0;
}

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