oj.uz

Submission #668109

# Submission time Handle Problem Language Result Execution time Memory
668109 2022-12-02T18:46:54 Z tibinyte Lampice (COCI19_lampice) C++17
110 / 110
 3357 ms 10212 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 25 ms 468 KB Output is correct
4 Correct 37 ms 600 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 8036 KB Output is correct
2 Correct 900 ms 8228 KB Output is correct
3 Correct 354 ms 9560 KB Output is correct
4 Correct 443 ms 9896 KB Output is correct
5 Correct 1030 ms 9532 KB Output is correct
6 Correct 229 ms 10212 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3357 ms 7424 KB Output is correct
2 Correct 2253 ms 7628 KB Output is correct
3 Correct 2380 ms 7084 KB Output is correct
4 Correct 1833 ms 8392 KB Output is correct
5 Correct 1631 ms 7188 KB Output is correct
6 Correct 1941 ms 6096 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 25 ms 468 KB Output is correct
4 Correct 37 ms 600 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1596 ms 8036 KB Output is correct
9 Correct 900 ms 8228 KB Output is correct
10 Correct 354 ms 9560 KB Output is correct
11 Correct 443 ms 9896 KB Output is correct
12 Correct 1030 ms 9532 KB Output is correct
13 Correct 229 ms 10212 KB Output is correct
14 Correct 3357 ms 7424 KB Output is correct
15 Correct 2253 ms 7628 KB Output is correct
16 Correct 2380 ms 7084 KB Output is correct
17 Correct 1833 ms 8392 KB Output is correct
18 Correct 1631 ms 7188 KB Output is correct
19 Correct 1941 ms 6096 KB Output is correct
20 Correct 1113 ms 6648 KB Output is correct
21 Correct 1022 ms 6776 KB Output is correct
22 Correct 1660 ms 6104 KB Output is correct
23 Correct 458 ms 6836 KB Output is correct
24 Correct 1676 ms 7612 KB Output is correct
25 Correct 1682 ms 7452 KB Output is correct
26 Correct 2410 ms 7572 KB Output is correct
27 Correct 2763 ms 6312 KB Output is correct
28 Correct 1353 ms 7080 KB Output is correct
29 Correct 1379 ms 7112 KB Output is correct
30 Correct 1964 ms 8260 KB Output is correct
31 Correct 1641 ms 7376 KB Output is correct
32 Correct 1247 ms 8672 KB Output is correct
33 Correct 579 ms 6972 KB Output is correct