Submission #655590

#	Time	Username	Problem	Language	Result	Execution time	Memory
655590		bebra	Lampice (COCI19_lampice)	C++17	110 / 110	4555 ms	16140 KiB

lampice

#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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37