oj.uz

Submission #1084843

# Submission time Handle Problem Language Result Execution time Memory
1084843 2024-09-07T05:54:06 Z nmts Lampice (COCI19_lampice) C++17
0 / 110
 5000 ms 9816 KB 
#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , "r" , stdin);freopen(name".out" , "w" , stdout);
#define faster    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
#define fi first
#define se second
#define mii map<int, int>
#define reset(a,val) memset(a ,val , sizeof(a))
#define endl '\n'    
#define ll long long
const int maxn = 5e4 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20;

using namespace std;

const int base = 311;

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

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

    void prepare() {
        n = 0;
        pw[0] = 1;
        for (int i = 1; i <= 50000; ++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() {
        for (int i = 1; i <= n; ++i) del[i] = 0;
    }

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

    int find_centroid(int u, int p) {
        for (int v : edges[u])
            if (v != p && !del[v])
                if (sz[v] > sz[u] / 2)
                    return find_centroid(v, u);
        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 1;

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

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

        hs.pop();
        return 0;
    }

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

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

        hs.pop();
        return 0;
    }

    bool decompose(int u, int len) {
        dfs(u, 0);
        int c = find_centroid(u, 0);
        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 1;

                    hs.clear();
                    hs.push(a[c]);

                    if (update(v, c, 2, len)) return 1;
                }

            reverse(edges[c].begin(), edges[c].end());
        }

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

        return 0;
    }
} 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)) ans = 2 * mid + ok, l = mid + 1;
        else r = mid - 1;
    }
}

void solve() {
    hs.prepare();

    cin >> n;
    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);  // tìm chuỗi palindrome có độ dài chẵn
    tknp(1, n >> 1, 1);  // tìm chuỗi palindrome có độ dài lẻ

    cout << ans << endl;
}

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5014 ms 9816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5050 ms 7772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -