oj.uz

Submission #1084657

# Submission time Handle Problem Language Result Execution time Memory
1084657 2024-09-06T16:01:31 Z anhthi Lampice (COCI19_lampice) C++14
110 / 110
 3557 ms 11168 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 8 ms 1740 KB Output is correct
3 Correct 31 ms 1628 KB Output is correct
4 Correct 28 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 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 1267 ms 10352 KB Output is correct
2 Correct 1191 ms 10252 KB Output is correct
3 Correct 753 ms 10412 KB Output is correct
4 Correct 942 ms 10884 KB Output is correct
5 Correct 1649 ms 11168 KB Output is correct
6 Correct 134 ms 9304 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2618 ms 8712 KB Output is correct
2 Correct 3557 ms 8500 KB Output is correct
3 Correct 2936 ms 8624 KB Output is correct
4 Correct 2810 ms 7276 KB Output is correct
5 Correct 2201 ms 8184 KB Output is correct
6 Correct 2145 ms 8024 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 8 ms 1740 KB Output is correct
3 Correct 31 ms 1628 KB Output is correct
4 Correct 28 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1267 ms 10352 KB Output is correct
9 Correct 1191 ms 10252 KB Output is correct
10 Correct 753 ms 10412 KB Output is correct
11 Correct 942 ms 10884 KB Output is correct
12 Correct 1649 ms 11168 KB Output is correct
13 Correct 134 ms 9304 KB Output is correct
14 Correct 2618 ms 8712 KB Output is correct
15 Correct 3557 ms 8500 KB Output is correct
16 Correct 2936 ms 8624 KB Output is correct
17 Correct 2810 ms 7276 KB Output is correct
18 Correct 2201 ms 8184 KB Output is correct
19 Correct 2145 ms 8024 KB Output is correct
20 Correct 1522 ms 6156 KB Output is correct
21 Correct 1754 ms 7712 KB Output is correct
22 Correct 2642 ms 7784 KB Output is correct
23 Correct 511 ms 4956 KB Output is correct
24 Correct 2311 ms 6188 KB Output is correct
25 Correct 2208 ms 6076 KB Output is correct
26 Correct 2782 ms 8816 KB Output is correct
27 Correct 2751 ms 8088 KB Output is correct
28 Correct 1760 ms 4900 KB Output is correct
29 Correct 1861 ms 5204 KB Output is correct
30 Correct 2104 ms 7388 KB Output is correct
31 Correct 1805 ms 5860 KB Output is correct
32 Correct 1612 ms 7804 KB Output is correct
33 Correct 1272 ms 7952 KB Output is correct