oj.uz

Submission #1084659

# Submission time Handle Problem Language Result Execution time Memory
1084659 2024-09-06T16:03:29 Z anhthi Lampice (COCI19_lampice) C++14
110 / 110
 3547 ms 10556 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;

const int mxn = 5e4 + 10, mxm = 3e6;
const int LG = 18, BASE = 311;

int n;
char a[mxn + 5];
vector<int> g[mxn + 5];

int pw[mxn + 5];

namespace CTDL {

    bool del[mxn + 5];
    int childs[mxn + 5];

    int getChilds(int u, int p) {
        childs[u] = 1;
        for (int v : g[u]) if (v != p && !del[v])
            childs[u] += getChilds(v, u);
        return childs[u];
    }
    int getCen(int u, int p, int sz) {
        for (int v : g[u]) if (v != p && !del[v]) {
            if (2 * childs[v] > sz) return getCen(v, u, sz);
        }
        return u;
    }
    int k;
    bool ans;
    int par[mxn + 5];
    int f[mxn + 5], h[mxn + 5];

    void prepare(int u, int p, int d = 1) {
        if (ans) return;
        if (d == k) {
            if (f[u] == h[u]) ans = true;
            return;
        }
        for (int v : g[u]) if (v != p && !del[v]) {
            par[v] = u;
            f[v] = (1LL * f[u] * BASE + a[v] - 'a' + 1) % mod;
            h[v] = (1LL * (a[v] - 'a' + 1) * pw[d] + h[u]) % mod;
            prepare(v, u, d + 1);
        }
        return;
    }

    gp_hash_table <int, bool> mark;

    int node[mxn + 5];
    void dfs(int u, int p, bool upd, int d = 2) {
        if (ans) return;
        if (d >= k) return;

        node[d] = u;
        if (upd) {
            int rem = k - d;
            if (d > rem) {
                int v = node[d - rem];
                if (f[v] == h[v])
                    ans = ans || mark[(f[u] - 1LL * f[par[v]] * pw[rem+1] + 1LL * mod * mod) % mod];
            }
        }
        else mark[f[u]] = true;

        for (int v : g[u]) if (v != p && !del[v])
            dfs(v, u, upd, d + 1);

        return;
    }

    void calc(int rt) {

        par[rt] = 0; node[1] = rt;

        f[rt] = h[rt] = a[rt] - 'a' + 1;
        prepare(rt, 0);

        if (ans) return;

        rep(i, 2) {
            mark.clear();
            for (int v : g[rt]) if (!del[v]) {
                dfs(v, rt, true);
                if (!ans)
                    dfs(v, rt, false);
                else return;
            }
            reverse(all(g[rt]));
        }

        return;
    }
    void solve(int u) {
        int sz = getChilds(u, 0);
        int cen = getCen(u, 0, sz);

        calc(cen);
        if (ans) return;

        del[cen] = true;
        for (int v : g[cen]) if (!del[v])
            solve(v);

        return;
    }

    bool ok(int _k) {

        k = _k;
        ans = false;
        memset(del, 0, (n + 5) * sizeof (bool));

        solve(1);

        return ans;
    }

}

int main(void) {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    rep(i, n) cin >> a[i];
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }

    pw[0] = 1;
    rep(i, n) pw[i] = 1LL * pw[i-1] * BASE % mod;

    int ans = 1;
    for (int l = 1, r = n / 2; l <= r; ) {
        int m = (l + r) >> 1;
        if (CTDL::ok(2 * m)) {
            maximize(ans, 2 * m); l = m + 1;
        }
        else r = m - 1;
    }
    for (int l = 1, r = n / 2; l <= r; ) {
        int m = (l + r) >> 1;
        if (CTDL::ok(2 * m + 1)) {
            maximize(ans, 2 * m + 1); l = m + 1;
        }
        else r = m - 1;
    }

    cout << ans;

    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1628 KB Output is correct
2 Correct 7 ms 1628 KB Output is correct
3 Correct 29 ms 1628 KB Output is correct
4 Correct 28 ms 1824 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1272 ms 9812 KB Output is correct
2 Correct 1222 ms 9688 KB Output is correct
3 Correct 737 ms 9944 KB Output is correct
4 Correct 893 ms 10292 KB Output is correct
5 Correct 1603 ms 10556 KB Output is correct
6 Correct 140 ms 8792 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2652 ms 8112 KB Output is correct
2 Correct 3547 ms 7912 KB Output is correct
3 Correct 2941 ms 8632 KB Output is correct
4 Correct 2779 ms 7192 KB Output is correct
5 Correct 2263 ms 8236 KB Output is correct
6 Correct 2107 ms 8196 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1628 KB Output is correct
2 Correct 7 ms 1628 KB Output is correct
3 Correct 29 ms 1628 KB Output is correct
4 Correct 28 ms 1824 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1272 ms 9812 KB Output is correct
9 Correct 1222 ms 9688 KB Output is correct
10 Correct 737 ms 9944 KB Output is correct
11 Correct 893 ms 10292 KB Output is correct
12 Correct 1603 ms 10556 KB Output is correct
13 Correct 140 ms 8792 KB Output is correct
14 Correct 2652 ms 8112 KB Output is correct
15 Correct 3547 ms 7912 KB Output is correct
16 Correct 2941 ms 8632 KB Output is correct
17 Correct 2779 ms 7192 KB Output is correct
18 Correct 2263 ms 8236 KB Output is correct
19 Correct 2107 ms 8196 KB Output is correct
20 Correct 1481 ms 6352 KB Output is correct
21 Correct 1722 ms 7692 KB Output is correct
22 Correct 2657 ms 7748 KB Output is correct
23 Correct 499 ms 4952 KB Output is correct
24 Correct 2282 ms 6172 KB Output is correct
25 Correct 2117 ms 6024 KB Output is correct
26 Correct 2732 ms 8776 KB Output is correct
27 Correct 2689 ms 7996 KB Output is correct
28 Correct 1758 ms 4952 KB Output is correct
29 Correct 1900 ms 5072 KB Output is correct
30 Correct 2200 ms 7452 KB Output is correct
31 Correct 1875 ms 5824 KB Output is correct
32 Correct 1628 ms 7976 KB Output is correct
33 Correct 1230 ms 8116 KB Output is correct