oj.uz

Submission #486765

# Submission time Handle Problem Language Result Execution time Memory
486765 2021-11-12T18:08:46 Z jalsol Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 11848 KB 
#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

using namespace std;

static const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
#define TASK "empty"
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    return true;
}();

using ll = long long;
using ld = long double;
#define fi first
#define se second

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 5e4 + 5;
constexpr int logn = 20;
constexpr int base = 31;

struct mint {
    int v;
    static constexpr int mod = 1e9 + 7;

    mint() : v(0) {}
    mint(ll _v) : v(int(_v % mod)) { v += (v < 0) * mod; }

    mint& operator+=(const mint& o) {
        if ((v += o.v) >= mod) v -= mod;
        return *this;
    }

    mint& operator-=(const mint& o) {
        if ((v -= o.v) < 0) v += mod;
        return *this;
    }

    mint& operator*=(const mint& o) {
        return *this = mint(1LL * v * o.v);
    }

    friend mint operator+(const mint& a, const mint& b) {
        return mint(a) += b;
    }
    friend mint operator-(const mint& a, const mint& b) {
        return mint(a) -= b;
    }
    friend mint operator*(const mint& a, const mint& b) {
        return mint(a) *= b;
    }

    friend bool operator==(const mint& a, const mint& b) {
        return a.v == b.v;
    }
    friend bool operator!=(const mint& a, const mint& b) {
        return a.v != b.v;
    }

    bool operator<(const mint& o) const {
        return v < o.v;
    }
};

int n;
char a[maxn];
vector<int> g[maxn];

mint power[maxn];
mint hdown[maxn], hup[maxn];

bool found;
bool rem[maxn];
int sz[maxn];

int up[maxn][logn];
int dep[maxn];

vector<int> node;
vector<pair<mint, int>> layer[maxn];

void getSz(int u, int p) {
    sz[u] = 1;
    Fe (v : g[u]) {
        if (rem[v] || v == p) continue;
        getSz(v, u);
        sz[u] += sz[v];
    }
}

int getCen(int target, int u, int p) {
    Fe (v : g[u]) {
        if (rem[v] || v == p) continue;
        if (sz[v] * 2 > target) return getCen(target, v, u);
    }
    return u;
}

void prepare(int u, int p) {
    node.push_back(u);
    layer[dep[u]].emplace_back(hdown[u], u);

    For (i, 1, logn - 1) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }

    Fe (v : g[u]) {
        if (rem[v] || v == p) continue;
        up[v][0] = u;
        dep[v] = dep[u] + 1;

        hdown[v] = hdown[u] * base + (a[v] - 'a' + 1);
        hup[v] = hup[u] + power[dep[v] - 1] * (a[v] - 'a' + 1);
        prepare(v, u);
    }
}

int lift(int u, int dist) {
    Repd (i, logn) {
        if (dist >> i & 1) u = up[u][i];
    }
    return u;
}

int getLca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);

    int dist = dep[u] - dep[v];
    u = lift(u, dist);

    if (u == v) return u;

    Repd (i, logn) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

mint getHash(int u, int v) {
    return hdown[u] - hdown[up[v][0]] * power[dep[u] - dep[v] + 1];
}

void calc(int u, int len) {
    if (found) return;

    hdown[u] = a[u] - 'a' + 1;
    hup[u] = a[u] - 'a' + 1;
    node.clear();
    up[u][0] = 0;
    dep[u] = 1;

    prepare(u, -1);

    For (i, 1, n) {
        sort(all(layer[i]));
    }

    Fe (A : node) {
        if (found) break;

        int odist = len - dep[A] + 1;
        if (odist > dep[A] || odist < 1) continue;

        const auto& cur = layer[odist];

        int C = lift(A, odist - 1);
        if (hdown[C] != hup[C]) continue;

        mint ohash = getHash(A, C);
        auto it = lower_bound(all(cur), pair(ohash, -1));

        if (it == cur.end()) {
            continue;
        }

        while (it != cur.end()) {
            if (it->fi != ohash) break;

            int B = it->se;

            if (getLca(A, B) == u) {
                found = true;
                break;
            } else {
                ++it;
            }
        }
    }

    For (i, 1, n) {
        layer[i].clear();
    }
}

void cd(int u, int len) {
    if (found) return;

    getSz(u, -1);
    u = getCen(sz[u], u, -1);
    rem[u] = true;

    calc(u, len);
    for (int v : g[u]) {
        if (rem[v] == false) {
            cd(v, len);
        }
    }
}

bool check(int len) {
    found = false;
    memset(rem, false, sizeof(rem));

    cd(1, len);

    return found;
}

signed main() {
    cin >> n >> (a + 1);

    Rep (_, n - 1) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    power[0] = 1;
    For (i, 1, n) power[i] = power[i - 1] * base;

    int l, r;
    int ans = 0;

    l = 0, r = n / 2;

    while (l <= r) {
        int m = (l + r) / 2;

        if (check(2 * m + 1)) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    chmax(ans, 2 * r + 1);

    l = 1, r = n / 2;

    while (l <= r) {
        int m = (l + r) / 2;

        if (check(2 * m)) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    chmax(ans, 2 * r);

    cout << ans << '\n';
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3404 KB Output is correct
2 Correct 24 ms 3516 KB Output is correct
3 Correct 82 ms 3532 KB Output is correct
4 Correct 150 ms 3660 KB Output is correct
5 Correct 2 ms 3276 KB Output is correct
6 Correct 2 ms 3276 KB Output is correct
7 Correct 3 ms 3276 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 11848 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 5091 ms 11336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3404 KB Output is correct
2 Correct 24 ms 3516 KB Output is correct
3 Correct 82 ms 3532 KB Output is correct
4 Correct 150 ms 3660 KB Output is correct
5 Correct 2 ms 3276 KB Output is correct
6 Correct 2 ms 3276 KB Output is correct
7 Correct 3 ms 3276 KB Output is correct
8 Execution timed out 5074 ms 11848 KB Time limit exceeded
9 Halted 0 ms 0 KB -