oj.uz

Submission #1115901

# Submission time Handle Problem Language Result Execution time Memory
1115901 2024-11-21T03:42:18 Z kzhi Lampice (COCI19_lampice) C++17
110 / 110
 1966 ms 29776 KB 
#include <bits/stdc++.h>

#define For(i, a, b) for (int i=a;i<=b;++i)

using namespace std;

const int N = 200005;
const long long base = 35711;
const long long mod  = 1e9 + 7;

int n, Len, maxDep, child[N], valid[N];
char a[N];

vector<pair<int, long long>> b;
long long pw[N];
vector<int> adj[N];
unordered_map<long long, bool> f[N];

void countChild(int u, int p)
{
    child[u] = 1;
    for (int v : adj[u]) if (v != p && valid[v])
    {
        countChild(v, u);
        child[u] += child[v];
    }
}

bool dfs(int u, int p, int h, long long hshdown, long long hshup)
{
    if (h > Len) return false;

    if (p)
        hshdown = (hshdown * base + a[u]) % mod;
    hshup = (hshup + 1LL * a[u] * pw[h - 1]) % mod;

    long long x =  (hshup * pw[Len - h] - hshdown + mod) % mod;
    if (!p) f[h][x] = true;

    if (f[Len - h + 1].find(x) != f[Len - h + 1].end() )
        return true;

    for (int v : adj[u]) if (v != p && valid[v])
    {
        if (!p) b.clear();

        if (dfs(v, u, h + 1, hshdown, hshup))
            return true;

        if (!p)
            for (pair<int, long long> x : b) f[x.first][x.second] = true;
    }

    maxDep = max(maxDep, h);
    b.push_back({h, x});

    return false;
}

bool CD(int u, int n)
{
    countChild(u, 0);

    int flag = 1, half = n / 2;
    while (flag)
    {
        flag = 0;
        for (int v : adj[u])
            if (valid[v] && child[v] < child[u] && child[v] > half)
            {
                u = v;
                flag = 1;
                break;
            }
    }

    countChild(u, 0);

    if (dfs(u, 0, 1, 0, 0)) return true;

    For(i, 1, maxDep) f[i].clear();
    maxDep = 0;

    valid[u] = false;
    for (int v : adj[u]) if (valid[v])
        if (CD(v, child[v])) return true;
    return false;
}

bool check(int len)
{
    Len = len;
    For(i, 1, n) valid[i] = 1, f[i].clear();
    return CD(1, n);
}

void solve()
{
    cin >> n;
    For(i, 1, n) cin >> a[i];
    For(i, 1, n - 1)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    pw[0] = 1;
    For(i, 1, n) pw[i] = pw[i - 1] * base % mod;

    int l = 0, r = (n - 1) / 2;
    while (l < r)
    {
        int g = (l + r + 1) / 2;
        if (check(g * 2 + 1)) l = g; else r = g - 1;
    }

    int ans = r * 2 + 1;

    l = 0, r = n / 2;
    while (l < r)
    {
        int g = (l + r + 1) / 2;
        if (check(g * 2)) l = g; else r = g - 1;
    }

    cout << max(ans, r * 2);
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    solve();

    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19024 KB Output is correct
2 Correct 7 ms 19168 KB Output is correct
3 Correct 17 ms 19024 KB Output is correct
4 Correct 20 ms 19196 KB Output is correct
5 Correct 4 ms 19024 KB Output is correct
6 Correct 4 ms 19192 KB Output is correct
7 Correct 4 ms 19024 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 28352 KB Output is correct
2 Correct 717 ms 28104 KB Output is correct
3 Correct 532 ms 28356 KB Output is correct
4 Correct 675 ms 28720 KB Output is correct
5 Correct 1030 ms 29776 KB Output is correct
6 Correct 100 ms 28356 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1605 ms 24528 KB Output is correct
2 Correct 1966 ms 23924 KB Output is correct
3 Correct 1762 ms 24832 KB Output is correct
4 Correct 1664 ms 24412 KB Output is correct
5 Correct 1418 ms 23412 KB Output is correct
6 Correct 1374 ms 23288 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19024 KB Output is correct
2 Correct 7 ms 19168 KB Output is correct
3 Correct 17 ms 19024 KB Output is correct
4 Correct 20 ms 19196 KB Output is correct
5 Correct 4 ms 19024 KB Output is correct
6 Correct 4 ms 19192 KB Output is correct
7 Correct 4 ms 19024 KB Output is correct
8 Correct 778 ms 28352 KB Output is correct
9 Correct 717 ms 28104 KB Output is correct
10 Correct 532 ms 28356 KB Output is correct
11 Correct 675 ms 28720 KB Output is correct
12 Correct 1030 ms 29776 KB Output is correct
13 Correct 100 ms 28356 KB Output is correct
14 Correct 1605 ms 24528 KB Output is correct
15 Correct 1966 ms 23924 KB Output is correct
16 Correct 1762 ms 24832 KB Output is correct
17 Correct 1664 ms 24412 KB Output is correct
18 Correct 1418 ms 23412 KB Output is correct
19 Correct 1374 ms 23288 KB Output is correct
20 Correct 984 ms 21716 KB Output is correct
21 Correct 1147 ms 22472 KB Output is correct
22 Correct 1532 ms 22812 KB Output is correct
23 Correct 377 ms 21072 KB Output is correct
24 Correct 1323 ms 23424 KB Output is correct
25 Correct 1197 ms 22220 KB Output is correct
26 Correct 1467 ms 24776 KB Output is correct
27 Correct 1538 ms 23020 KB Output is correct
28 Correct 992 ms 21196 KB Output is correct
29 Correct 1091 ms 21972 KB Output is correct
30 Correct 1208 ms 24512 KB Output is correct
31 Correct 1064 ms 22216 KB Output is correct
32 Correct 1063 ms 25028 KB Output is correct
33 Correct 655 ms 22948 KB Output is correct