Submission #1098538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098538		f0rizen	Lampice (COCI19_lampice)	C++17	110 / 110	4709 ms	11520 KiB

lampice

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

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;
}

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;

int len;
vector<int> a;
vector<vector<int>> g;
vector<bool> used;
vector<int> sz;
bool ok = false;
vector<int> dep;
vector<vector<int>> dp, rdp;
vector<int> up;
__gnu_pbds::gp_hash_table<int, bool> mp;

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

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

void dfs_ans(int v, int p = -1) {
    up.push_back(v);
    int k = len - dep[v] - 1;
    if (k > 0) {
        if (len - 2 * k > 0) {
            int u = up[(int) up.size() - (k + 1)];
            if (dp[1][u] == rdp[1][u]) {
                int h = sub(dp[1][v], mul(pw[k], dp[1][u]));
                if (mp.find(h) != mp.end()) {
                    ok = true;
                }
            }
        } else if (len - 2 * k == 0) {
            int h = dp[1][v];
            if (mp.find(h) != mp.end()) {
                ok = true;
            }
        }
    } else if (k == 0) {
        if (dp[1][v] == rdp[1][v]) {
            ok = true;
        }
    }
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            dfs_ans(u, v);
        }
    }
    up.pop_back();
}

void dfs_insert(int v, int p = -1) {
    if (dep[v] + 1 >= len) {
        return;
    }
    mp[dp[0][v]] = 1;
    for (auto u : g[v]) {
        if (u != p && !used[u]) {
            dfs_insert(u, v);
        }
    }
}

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;
}

void build(int v) {
    dep[v] = 0;
    dfs_sz(v);
    if (len == 1) {
        ok = true;
    }
    dp[0][v] = 0;
    rdp[0][v] = 0;
    dp[1][v] = a[v];
    rdp[1][v] = a[v];
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs_dp(u, v);
        }
    }
    up.push_back(v);
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs_ans(u, v);
            dfs_insert(u, v);
        }
    }
    up.pop_back();
    mp.clear();
    up.push_back(v);
    for (int i = (int) g[v].size() - 1; i >= 0; --i) {
        int u = g[v][i];
        if (!used[u]) {
            dfs_ans(u, v);
            dfs_insert(u, v);
        }
    }
    up.pop_back();
    mp.clear();
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            build(centroid(u, v, sz[u]));
        }
    }
}

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);
    }
    used.resize(n);
    sz.resize(n);
    dep.resize(n);
    dp.resize(2, vector<int>(n));
    rdp.resize(2, vector<int>(n));
    dfs_sz(0);
    int c = centroid(0, -1, 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;
            }
            len = 2 * mid;
            ok = false;
            fill(used.begin(), used.end(), 0);
            build(c);
            if (ok) {
                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;
            }
            len = 2 * mid + 1;
            ok = false;
            fill(used.begin(), used.end(), 0);
            build(c);
            if (ok) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ans = max(ans, 2 * l + 1);
    }
    cout << ans << "\n";
    return 0;
}

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