oj.uz

Submission #499004

# Submission time Handle Problem Language Result Execution time Memory
499004 2021-12-27T02:57:36 Z hoanghq2004 Lampice (COCI19_lampice) C++14
110 / 110
 4469 ms 12696 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int N = 5e4 + 10;
const int mod = 1e9 + 7;
const int base = 29;

int n, ti;
char c[N];
int big[N], sz[N], del[N];
vector <int> g[N];

void dfs(int u, int p) {
    big[u] = 0, sz[u] = 1;
    for (auto v: g[u]) {
        if (v == p || del[v] == ti) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[big[u]]) big[u] = v;
    }
}

int centroid(int u) {
    int num = sz[u] / 2;
    while (sz[big[u]] > num) u = big[u];
    return u;
}

// 2len + 2

int H[N], power[N];
int rH[N];

int get_hash(int L, int R) {
    return (0LL + H[R] - 1LL * H[L - 1] * power[R - L + 1] + 1LL * mod * mod) % mod;
}

int check(int u, int len) {
    dfs(u, 0);
    u = centroid(u);
    del[u] = ti;
    H[1] = c[u] - 'a' + 1;
    unordered_set <int> s;
    function <void(int, int, int)> add = [&](int u, int p, int d) {
        if (d > len) return;
        H[d] = (1LL * H[d - 1] * base + c[u] - 'a' + 1) % mod;
        s.insert(H[d]);
        for (auto v: g[u]) {
            if (v == p || del[v] == ti) continue;
            add(v, u, d + 1);
        }
    };
    rH[1] = c[u] - 'a' + 1;
    s.insert(H[1]);
    int ok = 0;
    function <void(int, int, int)> calc = [&](int u, int p, int d) {
        if (d > len || ok) return;
        H[d] = (1LL * H[d - 1] * base + c[u] - 'a' + 1) % mod;
        int rem = len - d + 1;
        rH[d] = (1LL * power[d - 1] * (c[u] - 'a' + 1) + rH[d - 1]) % mod;
        if (d * 2 - len > 0 && rH[d * 2 - len] == H[d * 2 - len]) {
            if (s.find(get_hash(d * 2 - len, d)) != s.end()) {
                ok = 1;
                return;
            }
        }
        for (auto v: g[u]) {
            if (v == p || del[v] == ti) continue;
            calc(v, u, d + 1);
        }
    };
    for (auto v: g[u]) {
        if (del[v] == ti) continue;
        calc(v, u, 2);
        if (ok) return 1;
        add(v, u, 2);
    }
    s.clear();
    reverse(g[u].begin(), g[u].end());
    for (auto v: g[u]) {
        if (del[v] == ti) continue;
        calc(v, u, 2);
        if (ok) return 1;
        add(v, u, 2);
    }
    for (auto v: g[u]) {
        if (del[v] == ti) continue;
        if (check(v, len)) return 1;
    }
    return 0;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = 1LL * power[i - 1] * base % mod;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    int L = 0, R = n / 2;
    while (R - L > 1) {
        int mid = L + R >> 1;
        ++ti;
        if (check(1, mid * 2)) L = mid;
        else R = mid;
    }
    ++ti;
    if (check(1, R * 2)) ans = R * 2;
    else ans = L * 2;
    if (!ans) ans = 1;
    L = 1, R = n / 2 + 1;
    while (R - L > 1) {
        int mid = L + R >> 1;
        ++ti;
        if (check(1, mid * 2 - 1)) L = mid;
        else R = mid;
    }
    ++ti;
    if (check(1, R * 2 - 1)) ans = max(ans, R * 2 - 1);
    else ans = max(ans, L * 2 - 1);
    cout << ans;
}

Compilation message

lampice.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
lampice.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
lampice.cpp: In lambda function:
lampice.cpp:63:13: warning: unused variable 'rem' [-Wunused-variable]
   63 |         int rem = len - d + 1;
      |             ^~~
lampice.cpp: In function 'int main()':
lampice.cpp:112:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid = L + R >> 1;
      |                   ~~^~~
lampice.cpp:123:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |         int mid = L + R >> 1;
      |                   ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 12 ms 1596 KB Output is correct
3 Correct 50 ms 1708 KB Output is correct
4 Correct 54 ms 1684 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2134 ms 11184 KB Output is correct
2 Correct 2209 ms 11428 KB Output is correct
3 Correct 1677 ms 11672 KB Output is correct
4 Correct 1905 ms 12096 KB Output is correct
5 Correct 2588 ms 12696 KB Output is correct
6 Correct 268 ms 10172 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3577 ms 8672 KB Output is correct
2 Correct 4469 ms 8300 KB Output is correct
3 Correct 4269 ms 8744 KB Output is correct
4 Correct 3834 ms 7176 KB Output is correct
5 Correct 3583 ms 7580 KB Output is correct
6 Correct 3384 ms 7036 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 12 ms 1596 KB Output is correct
3 Correct 50 ms 1708 KB Output is correct
4 Correct 54 ms 1684 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 2134 ms 11184 KB Output is correct
9 Correct 2209 ms 11428 KB Output is correct
10 Correct 1677 ms 11672 KB Output is correct
11 Correct 1905 ms 12096 KB Output is correct
12 Correct 2588 ms 12696 KB Output is correct
13 Correct 268 ms 10172 KB Output is correct
14 Correct 3577 ms 8672 KB Output is correct
15 Correct 4469 ms 8300 KB Output is correct
16 Correct 4269 ms 8744 KB Output is correct
17 Correct 3834 ms 7176 KB Output is correct
18 Correct 3583 ms 7580 KB Output is correct
19 Correct 3384 ms 7036 KB Output is correct
20 Correct 2392 ms 5116 KB Output is correct
21 Correct 2824 ms 6488 KB Output is correct
22 Correct 4180 ms 7860 KB Output is correct
23 Correct 1000 ms 4124 KB Output is correct
24 Correct 3135 ms 6460 KB Output is correct
25 Correct 2846 ms 5608 KB Output is correct
26 Correct 3859 ms 8188 KB Output is correct
27 Correct 3982 ms 8248 KB Output is correct
28 Correct 2432 ms 4184 KB Output is correct
29 Correct 2470 ms 4224 KB Output is correct
30 Correct 2917 ms 6716 KB Output is correct
31 Correct 2685 ms 5188 KB Output is correct
32 Correct 2362 ms 8196 KB Output is correct
33 Correct 2052 ms 6508 KB Output is correct