oj.uz

Submission #1098538

# Submission time Handle Problem Language Result Execution time Memory
1098538 2024-10-09T13:48:04 Z f0rizen Lampice (COCI19_lampice) C++17
110 / 110
 4709 ms 11520 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 35 ms 704 KB Output is correct
4 Correct 52 ms 616 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 10608 KB Output is correct
2 Correct 2264 ms 10848 KB Output is correct
3 Correct 2427 ms 11280 KB Output is correct
4 Correct 2456 ms 11408 KB Output is correct
5 Correct 2657 ms 11520 KB Output is correct
6 Correct 1725 ms 10148 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3736 ms 9308 KB Output is correct
2 Correct 4392 ms 9040 KB Output is correct
3 Correct 4391 ms 9024 KB Output is correct
4 Correct 3985 ms 7872 KB Output is correct
5 Correct 3701 ms 8588 KB Output is correct
6 Correct 3191 ms 8064 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 35 ms 704 KB Output is correct
4 Correct 52 ms 616 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1784 ms 10608 KB Output is correct
9 Correct 2264 ms 10848 KB Output is correct
10 Correct 2427 ms 11280 KB Output is correct
11 Correct 2456 ms 11408 KB Output is correct
12 Correct 2657 ms 11520 KB Output is correct
13 Correct 1725 ms 10148 KB Output is correct
14 Correct 3736 ms 9308 KB Output is correct
15 Correct 4392 ms 9040 KB Output is correct
16 Correct 4391 ms 9024 KB Output is correct
17 Correct 3985 ms 7872 KB Output is correct
18 Correct 3701 ms 8588 KB Output is correct
19 Correct 3191 ms 8064 KB Output is correct
20 Correct 1952 ms 6588 KB Output is correct
21 Correct 2149 ms 8136 KB Output is correct
22 Correct 3741 ms 8164 KB Output is correct
23 Correct 713 ms 5284 KB Output is correct
24 Correct 3950 ms 6624 KB Output is correct
25 Correct 3844 ms 6552 KB Output is correct
26 Correct 4709 ms 9280 KB Output is correct
27 Correct 3533 ms 8636 KB Output is correct
28 Correct 3008 ms 5592 KB Output is correct
29 Correct 3062 ms 5524 KB Output is correct
30 Correct 4030 ms 7056 KB Output is correct
31 Correct 3428 ms 6296 KB Output is correct
32 Correct 3320 ms 8352 KB Output is correct
33 Correct 1648 ms 8448 KB Output is correct