제출 #668046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668046		tibinyte	Lampice (COCI19_lampice)	C++14	17 / 110	5094 ms	12796 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
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<vector<int>> rmq;
    const int bsize = 15;
    void init(int _n)
    {
        n = _n;
        g = vector<vector<int>>(n + 1);
        colors = vector<char>(n + 1);
        seen = vector<bool>(n + 1);
        sz = depth = hashup = hashdown = vector<int>(n + 1);
        rmq = vector<vector<int>>(n + 1, vector<int>(bsize + 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 centroid = node;
        int mod = 1e9 + 7;
        int base = random(2, 2);
        int max_depth = 0;
        function<void(int, int, int)> dfs_init = [&](int node, int parent, int d)
        {
            rmq[node][0] = parent;
            for (int i = 1; i <= bsize; ++i)
            {
                rmq[node][i] = rmq[rmq[node][i - 1]][i - 1];
            }
            depth[node] = d;
            max_depth = max(max_depth, d);
            for (auto i : g[node])
            {

                if (i != parent && !seen[i])
                {
                    dfs_init(i, node, d + 1);
                }
            }
        };
        dfs_init(node, 0, 0);
        vector<int> power(max_depth + 1);
        power[0] = 1;
        for (int i = 1; i <= max_depth; ++i)
        {
            power[i] = (1ll * power[i - 1] * base) % mod;
        }
        function<void(int, int)> compute_hash = [&](int node, int parent)
        {
            hashup[node] = ((1ll * base * hashup[parent]) % mod + (colors[node] - 'a' + 1)) % mod;
            hashdown[node] = (hashdown[parent] + (1ll * power[depth[node]] * (colors[node] - 'a' + 1)) % mod) % mod;
            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 = rmq[b][0];
            return (hashup[a] - (1ll * hashup[c] * power[depth[a] - depth[c]]) % mod + mod) % mod;
        };
        function<int(int, int)> kth = [&](int node, int k)
        {
            int ans = node;
            for (int i = bsize; i >= 0; --i)
            {
                if (k & (1 << i))
                {
                    ans = rmq[ans][i];
                }
            }
            return ans;
        };
        set<int> exista;
        function<void(int, int, int)> add_subtree = [&](int node, int parent, int root)
        {
            exista.insert(get_hashup(node, root));
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    add_subtree(i, node, root);
                }
            }
        };
        bool este = false;
        function<void(int, int, int)> dfs = [&](int node, int parent, int d)
        {
            if (este)
            {
                return;
            }
            for (auto i : g[node])
            {
                if (i != parent && !seen[i])
                {
                    dfs(i, node, d + 1);
                }
            }
            int t = 2 * d - k;
            int l = k - d;
            if (t < 0 || l < 0)
            {
                return;
            }
            if (l == 0)
            {
                if (hashup[node] == hashdown[node])
                {
                    este = true;
                }
            }
            else
            {
                int qui = kth(node, l);
                if (hashup[qui] == hashdown[qui] && exista.find(get_hashup(node, kth(node, l - 1))) != exista.end())
                {
                    este = true;
                }
            }
        };
        for (auto i : g[node])
        {
            if (!seen[i])
            {
                dfs(i, node, 2);
                if (este)
                {
                    return este;
                }
                add_subtree(i, node, i);
            }
        }
        return false;
    }
    bool decomp(int node, int k)
    {
        if (k > n)
        {
            return false;
        }
        dfs_size(node, 0);
        node = find_centroid(node, 0, sz[node]);
        if (solve(node, k))
        {
            return true;
        }
        reverse(g[node].begin(), g[node].end());
        if (solve(node, k))
        {
            return true;
        }
        reverse(g[node].begin(), g[node].end());
        seen[node] = true;
        for (auto i : g[node])
        {
            if (!seen[i])
            {
                if (decomp(i, k))
                {
                    return true;
                }
            }
        }
        return false;
    }
    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;
    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 = 1, dr = n;
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

lampice.cpp: In member function 'bool lampice::solve(int, int)':
lampice.cpp:64:13: warning: unused variable 'centroid' [-Wunused-variable]
   64 |         int centroid = node;
      |             ^~~~~~~~

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