oj.uz

Submission #1099107

# Submission time Handle Problem Language Result Execution time Memory
1099107 2024-10-10T14:47:15 Z vux2code Lampice (COCI19_lampice) C++17
110 / 110
 2025 ms 27672 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 8 ms 15964 KB Output is correct
2 Correct 12 ms 16208 KB Output is correct
3 Correct 20 ms 16220 KB Output is correct
4 Correct 23 ms 16220 KB Output is correct
5 Correct 6 ms 16128 KB Output is correct
6 Correct 7 ms 15960 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 26068 KB Output is correct
2 Correct 688 ms 26324 KB Output is correct
3 Correct 482 ms 26580 KB Output is correct
4 Correct 611 ms 27092 KB Output is correct
5 Correct 973 ms 27672 KB Output is correct
6 Correct 98 ms 26764 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1691 ms 22772 KB Output is correct
2 Correct 2025 ms 22240 KB Output is correct
3 Correct 1736 ms 23244 KB Output is correct
4 Correct 1681 ms 22764 KB Output is correct
5 Correct 1293 ms 21712 KB Output is correct
6 Correct 1262 ms 21464 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15964 KB Output is correct
2 Correct 12 ms 16208 KB Output is correct
3 Correct 20 ms 16220 KB Output is correct
4 Correct 23 ms 16220 KB Output is correct
5 Correct 6 ms 16128 KB Output is correct
6 Correct 7 ms 15960 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct
8 Correct 741 ms 26068 KB Output is correct
9 Correct 688 ms 26324 KB Output is correct
10 Correct 482 ms 26580 KB Output is correct
11 Correct 611 ms 27092 KB Output is correct
12 Correct 973 ms 27672 KB Output is correct
13 Correct 98 ms 26764 KB Output is correct
14 Correct 1691 ms 22772 KB Output is correct
15 Correct 2025 ms 22240 KB Output is correct
16 Correct 1736 ms 23244 KB Output is correct
17 Correct 1681 ms 22764 KB Output is correct
18 Correct 1293 ms 21712 KB Output is correct
19 Correct 1262 ms 21464 KB Output is correct
20 Correct 878 ms 20052 KB Output is correct
21 Correct 1024 ms 20692 KB Output is correct
22 Correct 1466 ms 21116 KB Output is correct
23 Correct 357 ms 19404 KB Output is correct
24 Correct 1299 ms 21456 KB Output is correct
25 Correct 1223 ms 20684 KB Output is correct
26 Correct 1530 ms 22988 KB Output is correct
27 Correct 1577 ms 21704 KB Output is correct
28 Correct 1004 ms 19924 KB Output is correct
29 Correct 1085 ms 19892 KB Output is correct
30 Correct 1273 ms 22476 KB Output is correct
31 Correct 1068 ms 20692 KB Output is correct
32 Correct 1059 ms 23364 KB Output is correct
33 Correct 674 ms 20920 KB Output is correct