oj.uz

Submission #655590

# Submission time Handle Problem Language Result Execution time Memory
655590 2022-11-04T19:28:34 Z bebra Lampice (COCI19_lampice) C++17
110 / 110
 4555 ms 16140 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct pair_hash {
    template<typename T1, typename T2>
    std::size_t operator() (const std::pair<T1, T2>& pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

using my_set = unordered_set<pair<ll, int>, pair_hash>;

#define dbg(x) cerr << #x << ": " << x << endl;

// need to build first then search

const ll MOD = 1223376683;
const ll BASE = 449653;
// const ll BASE = 10;
const int MAX_N = 50000 + 5;
const int MAX_LOG = 17;

vector<int> g[MAX_N];

ll a[MAX_N];
ll powers[MAX_N];

ll hash_forward[MAX_N];
ll hash_reverse[MAX_N];

ll hash2_forward[MAX_N];
ll hash2_reverse[MAX_N];

ll curr_value[MAX_N];
ll curr_value2[MAX_N];

int sz[MAX_N];
bool used[MAX_N];
int dist[MAX_N];

bool found;
int curr_len;

inline void dfs_calc(int v, int p) {
    sz[v] = 1;
    for (int u : g[v]) {
        if (used[u] || u == p) continue;
        dfs_calc(u, v);
        sz[v] += sz[u];
    }
}

inline int find_centroid(int v, int p, int n) {
    for (int u : g[v]) {
        if (used[u] || u == p) continue;
        if (2 * sz[u] > n) {
            return find_centroid(u, v, n);
        }
    }
    return v;
}

inline void dfs_traverse(int v, int p, const my_set& curr_hashes) {
    dist[v] = dist[p] + 1;
    hash_forward[v] = (hash_forward[p] * BASE + a[v]) % MOD;
    hash_reverse[v] = (hash_reverse[p] + powers[dist[v]] * a[v]) % MOD;

    if (dist[p] == 0) {
        hash2_forward[v] = a[v];
        hash2_reverse[v] = a[v];
    } else {
        hash2_forward[v] = (hash2_forward[p] * BASE + a[v]) % MOD;
        hash2_reverse[v] = (hash2_reverse[p] + powers[dist[v] - 1] * a[v]) % MOD;
    }

    if (curr_len - dist[v] >= 1) {
        curr_value[v] = (hash_reverse[v] * powers[curr_len - dist[v] - 1] - hash_forward[v]) % MOD;
        if (curr_value[v] < 0) curr_value[v] += MOD;
    }
    if (curr_len - dist[v] >= 0) {
        ll curr = (hash2_reverse[v] * powers[curr_len - dist[v]] - hash2_forward[v]) % MOD;
        if (curr < 0) curr += MOD;

        if (curr_hashes.find(make_pair(curr, curr_len - dist[v] - 1)) != curr_hashes.end()) {
            found = true;
        }
    }

    if (hash_forward[v] == hash_reverse[v] && dist[v] + 1 == curr_len) {
        found = true;
    }

    if (dist[v] > curr_len) {
        return;
    }

    for (int u : g[v]) {
        if (used[u] || u == p) continue;
        dfs_traverse(u, v, curr_hashes);
    }
}

inline void dfs_apply(int v, int p, my_set& curr_hashes) {
    if (curr_len - dist[v] >= 0) {
        curr_hashes.insert(make_pair(curr_value[v], dist[v]));
    } else {
        return;
    }
    for (int u : g[v]) {
        if (used[u] || u == p) continue;
        dfs_apply(u, v, curr_hashes);
    }
}

inline void dfs_build(int v = 0) {
    dfs_calc(v, -1);
    int c = find_centroid(v, -1, sz[v]);
    used[c] = true;
    dist[c] = 0;
    hash_forward[c] = a[c];
    hash_reverse[c] = a[c];
    my_set curr_hashes;
    for (int u : g[c]) {
        if (!used[u]) {
            dfs_traverse(u, c, curr_hashes);
            dfs_apply(u, c, curr_hashes);
        }
    }
    for (int u : g[c]) {
        if (!used[u]) {
            dfs_build(u);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        a[i] = (int)(s[i] - 'a') + 1;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    powers[0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        powers[i] = (powers[i - 1] * BASE) % MOD;
    }
    int ans = 1;
    // binsearch on radius of palindrome
    // odd case
    {
        int l = 0;
        int r = n / 2 + 1;
        while (l != r - 1) {
            int m = (l + r) / 2;
            curr_len = 2 * m + 1;
            found = false;
            memset(used, 0, sizeof(used));
            if (curr_len > n) {
                r = m;
                continue;
            }
            dfs_build();    
            if (found) {
                l = m;
            } else {
                r = m;
            }
        }
        ans = max(ans, 2 * l + 1);
    }
    // even case
    {
        int l = 0;
        int r = n / 2 + 1;
        while (l != r - 1) {
            int m = (l + r) / 2;
            curr_len = 2 * m;
            found = false;
            memset(used, 0, sizeof(used));
            if (curr_len > n) {
                r = m;
                continue;
            }
            dfs_build();    
            if (found) {
                l = m;
            } else {
                r = m;
            }
        }
        ans = max(ans, 2 * l);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2004 KB Output is correct
2 Correct 11 ms 2024 KB Output is correct
3 Correct 37 ms 2260 KB Output is correct
4 Correct 54 ms 2260 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1720 ms 14372 KB Output is correct
2 Correct 2616 ms 14632 KB Output is correct
3 Correct 2922 ms 15020 KB Output is correct
4 Correct 3081 ms 15512 KB Output is correct
5 Correct 3116 ms 16140 KB Output is correct
6 Correct 2217 ms 13024 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3220 ms 12508 KB Output is correct
2 Correct 4321 ms 11884 KB Output is correct
3 Correct 4555 ms 12600 KB Output is correct
4 Correct 4002 ms 11144 KB Output is correct
5 Correct 3612 ms 11056 KB Output is correct
6 Correct 2881 ms 10172 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2004 KB Output is correct
2 Correct 11 ms 2024 KB Output is correct
3 Correct 37 ms 2260 KB Output is correct
4 Correct 54 ms 2260 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1720 ms 14372 KB Output is correct
9 Correct 2616 ms 14632 KB Output is correct
10 Correct 2922 ms 15020 KB Output is correct
11 Correct 3081 ms 15512 KB Output is correct
12 Correct 3116 ms 16140 KB Output is correct
13 Correct 2217 ms 13024 KB Output is correct
14 Correct 3220 ms 12508 KB Output is correct
15 Correct 4321 ms 11884 KB Output is correct
16 Correct 4555 ms 12600 KB Output is correct
17 Correct 4002 ms 11144 KB Output is correct
18 Correct 3612 ms 11056 KB Output is correct
19 Correct 2881 ms 10172 KB Output is correct
20 Correct 1989 ms 8232 KB Output is correct
21 Correct 2400 ms 10040 KB Output is correct
22 Correct 3700 ms 11924 KB Output is correct
23 Correct 636 ms 6884 KB Output is correct
24 Correct 3715 ms 9824 KB Output is correct
25 Correct 3434 ms 8756 KB Output is correct
26 Correct 4544 ms 12280 KB Output is correct
27 Correct 3407 ms 12492 KB Output is correct
28 Correct 2743 ms 7116 KB Output is correct
29 Correct 2654 ms 7216 KB Output is correct
30 Correct 3731 ms 9884 KB Output is correct
31 Correct 3069 ms 8240 KB Output is correct
32 Correct 3469 ms 11880 KB Output is correct
33 Correct 1812 ms 9980 KB Output is correct