oj.uz

Submission #893648

# Submission time Handle Problem Language Result Execution time Memory
893648 2023-12-27T08:39:13 Z now_or_never Lampice (COCI19_lampice) C++14
110 / 110
 1564 ms 29648 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;
            }
    }
    

    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 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 22 ms 19292 KB Output is correct
4 Correct 22 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 28360 KB Output is correct
2 Correct 711 ms 28620 KB Output is correct
3 Correct 481 ms 28876 KB Output is correct
4 Correct 604 ms 29392 KB Output is correct
5 Correct 937 ms 29648 KB Output is correct
6 Correct 94 ms 28880 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1290 ms 25052 KB Output is correct
2 Correct 1564 ms 24608 KB Output is correct
3 Correct 1391 ms 25304 KB Output is correct
4 Correct 1287 ms 25052 KB Output is correct
5 Correct 1022 ms 24024 KB Output is correct
6 Correct 988 ms 23768 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 22 ms 19292 KB Output is correct
4 Correct 22 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 725 ms 28360 KB Output is correct
9 Correct 711 ms 28620 KB Output is correct
10 Correct 481 ms 28876 KB Output is correct
11 Correct 604 ms 29392 KB Output is correct
12 Correct 937 ms 29648 KB Output is correct
13 Correct 94 ms 28880 KB Output is correct
14 Correct 1290 ms 25052 KB Output is correct
15 Correct 1564 ms 24608 KB Output is correct
16 Correct 1391 ms 25304 KB Output is correct
17 Correct 1287 ms 25052 KB Output is correct
18 Correct 1022 ms 24024 KB Output is correct
19 Correct 988 ms 23768 KB Output is correct
20 Correct 829 ms 22484 KB Output is correct
21 Correct 1049 ms 23076 KB Output is correct
22 Correct 1341 ms 23364 KB Output is correct
23 Correct 382 ms 21720 KB Output is correct
24 Correct 1098 ms 23608 KB Output is correct
25 Correct 1018 ms 22996 KB Output is correct
26 Correct 1332 ms 25292 KB Output is correct
27 Correct 1427 ms 23740 KB Output is correct
28 Correct 900 ms 21976 KB Output is correct
29 Correct 934 ms 21972 KB Output is correct
30 Correct 1045 ms 24532 KB Output is correct
31 Correct 877 ms 22992 KB Output is correct
32 Correct 910 ms 25500 KB Output is correct
33 Correct 704 ms 22928 KB Output is correct