oj.uz

답안 #499008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499008 2021-12-27T03:06:39 Z hoanghq2004 Lampice (COCI19_lampice) C++14
56 / 110
 4427 ms 12008 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;
}

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 * 2 > 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:61:13: warning: unused variable 'rem' [-Wunused-variable]
   61 |         int rem = len - d + 1;
      |             ^~~
lampice.cpp: In function 'int main()':
lampice.cpp:110:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid = L + R >> 1;
      |                   ~~^~~
lampice.cpp:121:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int mid = L + R >> 1;
      |                   ~~^~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 13 ms 1584 KB Output is correct
3 Correct 45 ms 1708 KB Output is correct
4 Incorrect 55 ms 1696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2045 ms 10200 KB Output is correct
2 Correct 2156 ms 10276 KB Output is correct
3 Correct 1654 ms 11600 KB Output is correct
4 Correct 1862 ms 12008 KB Output is correct
5 Correct 2586 ms 11592 KB Output is correct
6 Correct 286 ms 10192 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3420 ms 8256 KB Output is correct
2 Correct 4427 ms 8148 KB Output is correct
3 Correct 4228 ms 8396 KB Output is correct
4 Correct 3978 ms 7100 KB Output is correct
5 Correct 3279 ms 7508 KB Output is correct
6 Correct 3156 ms 6828 KB Output is correct

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 13 ms 1584 KB Output is correct
3 Correct 45 ms 1708 KB Output is correct
4 Incorrect 55 ms 1696 KB Output isn't correct
5 Halted 0 ms 0 KB -