oj.uz

Submission #1021473

# Submission time Handle Problem Language Result Execution time Memory
1021473 2024-07-12T18:40:33 Z LOLOLO Lampice (COCI19_lampice) C++14
110 / 110
 2001 ms 14168 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 50000 + 10;
ll mod = 1e9 + 7;
ll pw[N];
ll base = 256;
map <ll, bool> mp[N];
ll a[N];
int n;
bool vis[N];
int sz[N];
vector <int> ed[N];
 
void dfs(int u, int v) {
    sz[u] = 1;
    for (auto x : ed[u]) {
        if (x == v || vis[x])
            continue;
 
        dfs(x, u);
        sz[u] += sz[x];
    }
}
 
int find_centroid(int u, int v, int ss) {
    for (auto x : ed[u]) {
        if (x == v || vis[x])
            continue;
 
        if (sz[x] * 2 > ss)
            return find_centroid(x, u, ss);
    }
 
    return u;
}
 
int mx = 0, len = 0, root = 0;
 
void run(int u, int v, int upd, int h, ll up, ll down, int &is) {
    mx = max(mx, h);
    up = (up * base + a[u]) % mod;
    down = (down + pw[h - 1] * a[u]) % mod;
    ll val = (down * pw[len - h] - up + mod) % mod;
    if (upd) {
        mp[h][val] = 1;
    } else {
        if (h + 1 == len && (down * base + root) % mod == up) {
            is = 1;
            return;
        }
 
        if (len > h && mp[len - h - 1].find(val) != mp[len - h - 1].end()) {
            is = 1;
            return;
        }
    }
 
    if (h < len) {
        for (auto x : ed[u]) {
            if (x == v || vis[x])
                continue;
 
            run(x, u, upd, h + 1, up, down, is);
            mx = max(mx, h + 1);
            if (is)
                return;
        }
    }
}
 
void process(int u, int &is) {
    dfs(u, 0);
    int cen = find_centroid(u, 0, sz[u]);
    vis[cen] = 1;
    root = a[cen];
    mx = 0;
 
    for (auto x : ed[cen]) {
        if (vis[x])
            continue;
 
        run(x, 0, 0, 1, root, 0, is);
        if (is)
            return;
 
        run(x, 0, 1, 1, root, 0, is);
    }
 
    for (int i = 0; i <= mx; i++)
        mp[i].clear();
 
    for (auto x : ed[cen]) {
        if (vis[x])
            continue;
 
        process(x, is);
        if (is)
            return;
    }
}
 
bool check(int x) {
    for (int i = 0; i <= n; i++)
        mp[i].clear();
 
    mem(vis, 0);
    int is = 0;
    len = x;
    process(1, is);
    return is;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    string str;
    cin >> str;
    str = '0' + str;
 
    for (int i = 1; i <= n; i++)
        a[i] = (str[i] - 'a' + 1);
 
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = (pw[i - 1] * base) % mod; 
 
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }
 
    int ans = 1;
    for (int i = 0; i < 2; i++) {
        int l = 0, r = n / 2 + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (check(m * 2 + i)) {
                ans = max(ans, m * 2 + i);
                l = m;
            } else {
                r = m;
            }
        }
    }
 
 
    cout << ans << '\n';
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3928 KB Output is correct
2 Correct 6 ms 3944 KB Output is correct
3 Correct 18 ms 4240 KB Output is correct
4 Correct 17 ms 4220 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 12896 KB Output is correct
2 Correct 687 ms 12888 KB Output is correct
3 Correct 454 ms 13364 KB Output is correct
4 Correct 590 ms 13656 KB Output is correct
5 Correct 1006 ms 14168 KB Output is correct
6 Correct 102 ms 12692 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1501 ms 11448 KB Output is correct
2 Correct 2001 ms 11076 KB Output is correct
3 Correct 1756 ms 11356 KB Output is correct
4 Correct 1562 ms 10072 KB Output is correct
5 Correct 1318 ms 10328 KB Output is correct
6 Correct 1212 ms 9908 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3928 KB Output is correct
2 Correct 6 ms 3944 KB Output is correct
3 Correct 18 ms 4240 KB Output is correct
4 Correct 17 ms 4220 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 681 ms 12896 KB Output is correct
9 Correct 687 ms 12888 KB Output is correct
10 Correct 454 ms 13364 KB Output is correct
11 Correct 590 ms 13656 KB Output is correct
12 Correct 1006 ms 14168 KB Output is correct
13 Correct 102 ms 12692 KB Output is correct
14 Correct 1501 ms 11448 KB Output is correct
15 Correct 2001 ms 11076 KB Output is correct
16 Correct 1756 ms 11356 KB Output is correct
17 Correct 1562 ms 10072 KB Output is correct
18 Correct 1318 ms 10328 KB Output is correct
19 Correct 1212 ms 9908 KB Output is correct
20 Correct 1173 ms 8236 KB Output is correct
21 Correct 1506 ms 9304 KB Output is correct
22 Correct 1952 ms 9788 KB Output is correct
23 Correct 403 ms 7260 KB Output is correct
24 Correct 1310 ms 8792 KB Output is correct
25 Correct 1226 ms 8144 KB Output is correct
26 Correct 1614 ms 10888 KB Output is correct
27 Correct 1933 ms 10324 KB Output is correct
28 Correct 925 ms 7504 KB Output is correct
29 Correct 988 ms 7260 KB Output is correct
30 Correct 1184 ms 9560 KB Output is correct
31 Correct 1010 ms 8020 KB Output is correct
32 Correct 1075 ms 10672 KB Output is correct
33 Correct 1129 ms 10036 KB Output is correct