Submission #486774

#	Time	Username	Problem	Language	Result	Execution time	Memory
486774		jalsol	Lampice (COCI19_lampice)	C++17	17 / 110	5085 ms	12224 KiB

lampice

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

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

namespace KACTL {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wshadow"
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>

// content goes here

struct H {
	typedef uint64_t ull;
	ull x; H(ull x=0) : x(x) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
	(A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
	OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx")
	H operator-(H o) { return *this + ~o.x; }
	ull get() const { return x + !~x; }
	bool operator==(H o) const { return get() == o.get(); }
	bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)

struct HashInterval {
	vector<H> ha, pw;
	HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
		pw[0] = 1;
		rep(i,0,sz(str))
			ha[i+1] = ha[i] * C + str[i],
			pw[i+1] = pw[i] * C;
	}
	H hashInterval(int a, int b) { // hash [a, b)
		return ha[b] - ha[a] * pw[b - a];
	}
};

vector<H> getHashes(string& str, int length) {
	if (sz(str) < length) return {};
	H h = 0, pw = 1;
	rep(i,0,length)
		h = h * C + str[i], pw = pw * C;
	vector<H> ret = {h};
	rep(i,length,sz(str)) {
		ret.push_back(h = h * C + str[i] - pw * str[i-length]);
	}
	return ret;
}

H hashString(string& s){H h{}; for(char c:s) h=h*C+c;return h;}

// content ends here

#undef rep
#undef sz
#undef pii
#undef vi
#pragma GCC diagnostic pop
} // namespace KACTL
using namespace KACTL;

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

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

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

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

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

vector<int> node;
vector<pair<H, 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];
}

H 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].x != hup[C].x) continue;

        H 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.x != ohash.x) 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 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37