Submission #668109

#	Time	Username	Problem	Language	Result	Execution time	Memory
668109		tibinyte	Lampice (COCI19_lampice)	C++17	110 / 110	3357 ms	10212 KiB

lampice

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 9;

int add(int x, int y)
{
    x += y;
    if (x >= mod)
    {
        return x - mod;
    }
    return x;
}

int mult(int x, int y)
{
    return (int64_t)x * y % mod;
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int st, int dr)
{
    uniform_int_distribution<mt19937::result_type> gen(st, dr);
    return gen(rng);
}
struct lampice
{
    int n;
    vector<vector<int>> g;
    vector<char> colors;
    vector<bool> seen;
    vector<int> sz;
    vector<int> depth;
    vector<int> hashup;
    vector<int> hashdown;
    vector<int> par;
    vector<int> nodes;
    vector<int> neortodox;
    vector<int> dp;
    void init(int _n)
    {
        n = _n;
        g = vector<vector<int>>(n + 1);
        colors = vector<char>(n + 1);
        seen = vector<bool>(n + 1);
        dp = neortodox = nodes = sz = depth = hashup = hashdown = par = vector<int>(n + 1);
    }
    void set_color(int pos, char x)
    {
        colors[pos] = x;
    }
    void add_edge(int a, int b)
    {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void dfs_size(int node, int parent)
    {
        sz[node] = 1;
        for (auto i : g[node])
        {
            if (i != parent && !seen[i])
            {
                dfs_size(i, node);
                sz[node] += sz[i];
            }
        }
    }
    int find_centroid(int node, int parent, int size)
    {
        for (auto i : g[node])
        {
            if (i != parent && !seen[i] && sz[i] > size / 2)
            {
                return find_centroid(i, node, size);
            }
        }
        return node;
    }
    bool solve(int node, int k)
    {
        int base = random(29, 50);
        int max_depth = 0;
        function<void(int, int, int)> dfs_init = [&](int node, int parent, int d)
        {
            par[node] = parent;
            depth[node] = d;
            dp[node] = 1;
            max_depth = max(max_depth, d);
            for (auto i : g[node])
            {

                if (i != parent && !seen[i])
                {
                    dfs_init(i, node, d + 1);
                    dp[node] = max(dp[node], dp[i] + 1);
                }
            }
            int mx1 = 0, mx2 = 0;
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    if (dp[i] > mx1)
                    {
                        mx2 = mx1;
                        mx1 = dp[i];
                    }
                    else
                    {
                        if (dp[i] > mx2)
                        {
                            mx2 = dp[i];
                        }
                    }
                }
            }
            neortodox[node] = mx1 + mx2 + 1;
        };
        dfs_init(node, 0, 0);
        if (neortodox[node] < k)
        {
            return 0;
        }
        vector<int> power(max_depth + 1);
        power[0] = 1;
        for (int i = 1; i <= max_depth; ++i)
        {
            power[i] = mult(power[i - 1], base);
        }
        function<void(int, int)> compute_hash = [&](int node, int parent)
        {
            hashup[node] = add(mult(base, hashup[parent]), colors[node] - 'a' + 1);
            hashdown[node] = add(hashdown[parent], mult(power[depth[node]], (colors[node] - 'a' + 1)));
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    compute_hash(i, node);
                }
            }
        };
        compute_hash(node, 0);
        function<int(int, int)> get_hashup = [&](int a, int b)
        {
            int c = par[b];
            return add(hashup[a], mod - mult(hashup[c], power[depth[a] - depth[c]]));
        };
        unordered_multiset<int> exista;
        function<void(int, int, int, int)> add_subtree = [&](int node, int parent, int root, int d)
        {
            if (d + d <= k)
            {
                exista.insert(get_hashup(node, root));
            }
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    add_subtree(i, node, root, d + 1);
                }
            }
        };
        function<void(int, int, int, int)> remove_subtree = [&](int node, int parent, int root, int d)
        {
            if (d + d <= k)
            {
                exista.erase(exista.find(get_hashup(node, root)));
            }
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    remove_subtree(i, node, root, d + 1);
                }
            }
        };
        bool este = false;
        int m = 1;
        nodes[1] = node;
        function<void(int, int, int)> dfs = [&](int node, int parent, int d)
        {
            if (este)
            {
                return;
            }
            nodes[++m] = node;
            int t = 2 * d - k;
            int l = k - d;
            if (l >= 0 && t >= 0)
            {
                if (l == 0)
                {
                    if (hashup[node] == hashdown[node])
                    {
                        este = true;
                    }
                }
                else
                {
                    int qui = nodes[m - l];
                    if (hashup[qui] == hashdown[qui] && exista.count(get_hashup(node, nodes[m - l + 1])))
                    {
                        este = true;
                    }
                }
            }
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    dfs(i, node, d + 1);
                }
            }
            --m;
        };
        for (auto i : g[node])
        {
            if (!seen[i])
            {
                add_subtree(i, node, i, 1);
            }
        }
        for (auto i : g[node])
        {
            if (!seen[i])
            {
                remove_subtree(i, node, i, 1);
                dfs(i, node, 2);
                if (este)
                {
                    break;
                }
                add_subtree(i, node, i, 1);
            }
        }
        return este;
    }
    bool decomp(int node, int k)
    {
        dfs_size(node, 0);
        node = find_centroid(node, 0, sz[node]);
        int ans = solve(node, k);
        seen[node] = true;
        for (auto i : g[node])
        {
            if (ans)
            {
                break;
            }
            if (!seen[i])
            {
                ans |= decomp(i, k);
            }
        }
        return ans;
    }
    void reinit()
    {
        seen = vector<bool>(n + 1);
    }
};
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    lampice g;
    g.init(n);
    for (int i = 1; i <= n; ++i)
    {
        char x;
        cin >> x;
        g.set_color(i, x);
    }
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        g.add_edge(u, v);
    }
    int ans = 1;
    int st = 1, dr = n / 2;
    while (st <= dr)
    {
        int mid = (st + dr) / 2;
        if (g.decomp(1, 2 * mid))
        {
            ans = max(ans, 2 * mid);
            st = mid + 1;
        }
        else
        {
            dr = mid - 1;
        }
        g.reinit();
    }
    st = max(1, ans / 2), dr = n / 2;
    while (st <= dr)
    {
        int mid = (st + dr) / 2;
        if (g.decomp(1, 2 * mid + 1))
        {
            ans = max(ans, 2 * mid + 1);
            st = mid + 1;
        }
        else
        {
            dr = mid - 1;
        }
        g.reinit();
    }
    cout << ans;
}

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