Submission #1084864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084864	2024-09-07T06:22:27 Z	nmts	Lampice (COCI19_lampice)	C++17	Compilation error	0 ms	0 KB

lampice

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ll long long
const int maxn = 5e4 + 6;

using namespace std;
using namespace __gnu_pbds;

const int base = 311;

int n;
basic_string<int> edges[maxn];
int ans = 1;
char a[maxn];
gp_hash_table<ll, bool> m;

struct Hash {
    ll pw[maxn], hash_val[maxn], pre_hash[maxn];
    int n;

    void prepare(int sz) {
        n = 0;
        pw[0] = 1;
        for (int i = 1; i <= sz; ++i)
            pw[i] = pw[i - 1] * base;
    }

    void push(char c) {
        n++;
        hash_val[n] = hash_val[n - 1] * base + c;
        pre_hash[n] = pre_hash[n - 1] + c * pw[n - 1];
    }

    void pop() {
        n--;
    }

    void clear() {
        n = 0;
    }

    bool IsPalin(int l) {
        return hash_val[l] == pre_hash[l];
    }

    ll get(int l) {
        return hash_val[n] - hash_val[n - l] * pw[l];
    }
} hs;

struct CD {
    int sz[maxn];
    bool del[maxn];

    void init() {
        memset(del, 0, sizeof(del)); // nhanh hơn vòng for
    }

    void dfs(int u, int p) {
        sz[u] = 1;
        for (int v : edges[u])
            if (v != p && !del[v]) {
                dfs(v, u);
                sz[u] += sz[v];
            }
    }

    int find_centroid(int u, int p, int total_size) {
        for (int v : edges[u])
            if (v != p && !del[v] && sz[v] > total_size / 2)
                return find_centroid(v, u, total_size);
        return u;
    }

    bool get(int u, int p, int height, int len) {
        hs.push(a[u]);
        if (2 * height <= len && m[hs.get(height)]) return true;
        if (height == len && hs.IsPalin(len)) return true;

        for (int v : edges[u])
            if (v != p && !del[v])
                if (get(v, u, height + 1, len)) return true;

        hs.pop();
        return false;
    }

    bool update(int u, int p, int height, int len) {
        hs.push(a[u]);
        if (height * 2 >= len && hs.IsPalin(height * 2 - len))
            m[hs.get(len - height)] = 1;

        if (height == len && hs.IsPalin(len)) return true;

        for (int v : edges[u])
            if (v != p && !del[v])
                if (update(v, u, height + 1, len)) return true;

        hs.pop();
        return false;
    }

    bool decompose(int u, int len) {
        dfs(u, 0);
        int total_size = sz[u];
        int c = find_centroid(u, 0, total_size);
        del[c] = 1;

        for (int turn = 1; turn <= 2; ++turn) {
            m.clear();
            for (int v : edges[c]) {
                if (!del[v]) {
                    hs.clear();
                    if (get(v, c, 1, len)) return true;

                    hs.clear();
                    hs.push(a[c]);
                    if (update(v, c, 2, len)) return true;
                }
            }
            reverse(edges[c].begin(), edges[c].end());  // để đảm bảo không bỏ sót cạnh nào
        }

        for (int v : edges[c])
            if (!del[v])
                if (decompose(v, len)) return true;

        return false;
    }
} cd;

void tknp(int l, int r, int ok) {
    while (l <= r) {
        int mid = (l + r) >> 1;
        cd.init();
        if (cd.decompose(1, 2 * mid + ok))
            maximize(ans, 2 * mid + ok), l = mid + 1;
        else
            r = mid - 1;
    }
}

void solve() {
    cin >> n;
    hs.prepare(n + 1);

    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    tknp(1, n >> 1, 0);
    tknp(1, n >> 1, 1);

    cout << ans << endl;
}

int32_t main() {
    faster;
    solve();
    return 0;
}

Compilation message

lampice.cpp: In function 'void tknp(int, int, int)':
lampice.cpp:139:13: error: 'maximize' was not declared in this scope
  139 |             maximize(ans, 2 * mid + ok), l = mid + 1;
      |             ^~~~~~~~