oj.uz

Submission #921160

# Submission time Handle Problem Language Result Execution time Memory
921160 2024-02-03T11:18:40 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 4802 ms 63932 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 31;

int n, sz[N], Pow[N], dep[N], up[N], down[N];
string s;
vector<int> g[N];
bool del[N];
unordered_map<int, bool> mp[N];
int mx, centroid, len;

int dfs_size(int u, int p = 0) {
    sz[u] = 1;
    for(int v : g[u]) if(v != p && !del[v]) {
        sz[u] += dfs_size(v, u);
    }
    return sz[u];
}

int find_centroid(int u, int p, int num) {
    for(int v : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num);
    return u;
}

void dfs_centroid(int u, int p, bool upd, bool &found) {
    dep[u] = dep[p] + 1;
    up[u] = (1ll * up[p] * base + s[u] - 'a' + 1) % mod;
    down[u] = (down[p] + 1ll * Pow[dep[u] - 1] * (s[u] - 'a' + 1)) % mod;
    int val = (1ll * down[u] * Pow[len - dep[u]] - up[u]) % mod; if(val < 0) val += mod;
    if(upd) mp[dep[u]][val] = 1;
    else {
        if(dep[u] + 1 == len && up[u] == (1ll * down[u] * base + s[centroid] - 'a' + 1) % mod) {
            found = 1;
            return;
        }
        if(dep[u] < len && mp[len - dep[u] - 1][val]) {
            found = 1;
            return;
        }
    }
    if(dep[u] < len) {
        for(int v : g[u]) if(v != p && !del[v])  {
            dfs_centroid(v, u, upd, found);
            mx = max(mx, dep[u] + 1);
            if(found) return;
        }
    }
}

void calc(int u, bool &found) {
    centroid = find_centroid(u, 0, dfs_size(u));
    del[centroid] = 1;
    mx = 1;
    up[centroid] = s[centroid] - 'a' + 1;
    down[centroid] = 0;
    dep[centroid] = 0;
    for(int v : g[centroid]) if(!del[v]) {
        dfs_centroid(v, centroid, 0, found);
        if(found) return;
        dfs_centroid(v, centroid, 1, found);
    }
    for(int i = 0; i <= mx; ++i) mp[i].clear();
    for(int v : g[centroid]) if(!del[v]) {
        calc(v, found);
        if(found) return;
    }

}

bool check(int x) {
    for(int i = 0; i <= n; ++i) mp[i].clear();
    memset(del, 0, sizeof(del));
    bool found = 0; len = x;
    calc(1, found);
    return found;
}

void solve() {
    cin >> n >> s; s = ' ' + s;
    Pow[0] = 1; for(int i = 1; i <= n; ++i) Pow[i] = (1ll * Pow[i - 1] * base) % mod;
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    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 >> 1;
            if(check(i + 2 * m)) l = m;
            else r = m;
        }
        ans = max(ans, i + 2 * l);
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

// https://oj.uz/problem/view/COCI19_lampice

Compilation message

lampice.cpp: In function 'void solve()':
lampice.cpp:93:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 8 ms 4700 KB Output is correct
3 Correct 28 ms 5208 KB Output is correct
4 Correct 26 ms 4952 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1646 ms 30264 KB Output is correct
2 Correct 2618 ms 48256 KB Output is correct
3 Correct 1233 ms 31376 KB Output is correct
4 Correct 1864 ms 32744 KB Output is correct
5 Correct 3634 ms 57176 KB Output is correct
6 Correct 209 ms 16984 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2956 ms 40764 KB Output is correct
2 Correct 4802 ms 56080 KB Output is correct
3 Correct 3598 ms 37960 KB Output is correct
4 Correct 2000 ms 13288 KB Output is correct
5 Correct 3278 ms 51672 KB Output is correct
6 Correct 2221 ms 30704 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 8 ms 4700 KB Output is correct
3 Correct 28 ms 5208 KB Output is correct
4 Correct 26 ms 4952 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1646 ms 30264 KB Output is correct
9 Correct 2618 ms 48256 KB Output is correct
10 Correct 1233 ms 31376 KB Output is correct
11 Correct 1864 ms 32744 KB Output is correct
12 Correct 3634 ms 57176 KB Output is correct
13 Correct 209 ms 16984 KB Output is correct
14 Correct 2956 ms 40764 KB Output is correct
15 Correct 4802 ms 56080 KB Output is correct
16 Correct 3598 ms 37960 KB Output is correct
17 Correct 2000 ms 13288 KB Output is correct
18 Correct 3278 ms 51672 KB Output is correct
19 Correct 2221 ms 30704 KB Output is correct
20 Correct 1320 ms 16156 KB Output is correct
21 Correct 2157 ms 42076 KB Output is correct
22 Correct 3961 ms 63932 KB Output is correct
23 Correct 474 ms 8284 KB Output is correct
24 Correct 1960 ms 22096 KB Output is correct
25 Correct 1659 ms 18060 KB Output is correct
26 Correct 3061 ms 32964 KB Output is correct
27 Correct 3258 ms 46564 KB Output is correct
28 Correct 1143 ms 7760 KB Output is correct
29 Correct 1295 ms 7920 KB Output is correct
30 Correct 1440 ms 11848 KB Output is correct
31 Correct 1246 ms 10496 KB Output is correct
32 Correct 1862 ms 32108 KB Output is correct
33 Correct 2894 ms 47352 KB Output is correct