oj.uz

Submission #921145

# Submission time Handle Problem Language Result Execution time Memory
921145 2024-02-03T11:03:29 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 4881 ms 63892 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];
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, int dep, int up, int down, bool &found) {
    up = (1ll * up * base + s[u] - 'a' + 1) % mod;
    down = (down + 1ll * Pow[dep - 1] * (s[u] - 'a' + 1)) % mod;
    int val = (1ll * down * Pow[len - dep] - up) % mod; if(val < 0) val += mod;
    if(upd) mp[dep][val] = 1;
    else {
        if(dep + 1 == len && up == (1ll * down * base + s[centroid] - 'a' + 1) % mod) {
            found = 1;
            return;
        }
        if(dep < len && mp[len - dep - 1][val]) {
            found = 1;
            return;
        }
    }
    if(dep < len) {
        for(int v : g[u]) if(v != p && !del[v])  {
            dfs_centroid(v, u, upd, dep + 1, up, down, found);
            mx = max(mx, dep + 1);
            if(found) return;
        }
    }
}

void calc(int u, bool &found) {
    centroid = find_centroid(u, 0, dfs_size(u));
    del[centroid] = 1;
    mx = 1;
    for(int v : g[centroid]) if(!del[v]) {
        dfs_centroid(v, centroid, 0, 1, s[centroid] - 'a' + 1, 0, found);
        if(found) return;
        dfs_centroid(v, centroid, 1, 1, s[centroid] - 'a' + 1, 0, 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:89:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 28 ms 5404 KB Output is correct
4 Correct 24 ms 4956 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4740 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1529 ms 30096 KB Output is correct
2 Correct 2996 ms 48364 KB Output is correct
3 Correct 1228 ms 31328 KB Output is correct
4 Correct 1759 ms 33220 KB Output is correct
5 Correct 3783 ms 57096 KB Output is correct
6 Correct 184 ms 16980 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2904 ms 40928 KB Output is correct
2 Correct 4881 ms 56140 KB Output is correct
3 Correct 3547 ms 38016 KB Output is correct
4 Correct 1834 ms 13740 KB Output is correct
5 Correct 3329 ms 51716 KB Output is correct
6 Correct 2224 ms 30832 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 28 ms 5404 KB Output is correct
4 Correct 24 ms 4956 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4740 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1529 ms 30096 KB Output is correct
9 Correct 2996 ms 48364 KB Output is correct
10 Correct 1228 ms 31328 KB Output is correct
11 Correct 1759 ms 33220 KB Output is correct
12 Correct 3783 ms 57096 KB Output is correct
13 Correct 184 ms 16980 KB Output is correct
14 Correct 2904 ms 40928 KB Output is correct
15 Correct 4881 ms 56140 KB Output is correct
16 Correct 3547 ms 38016 KB Output is correct
17 Correct 1834 ms 13740 KB Output is correct
18 Correct 3329 ms 51716 KB Output is correct
19 Correct 2224 ms 30832 KB Output is correct
20 Correct 1231 ms 16104 KB Output is correct
21 Correct 2056 ms 42004 KB Output is correct
22 Correct 3901 ms 63892 KB Output is correct
23 Correct 440 ms 8260 KB Output is correct
24 Correct 1884 ms 22356 KB Output is correct
25 Correct 1599 ms 17768 KB Output is correct
26 Correct 2889 ms 33364 KB Output is correct
27 Correct 3196 ms 46668 KB Output is correct
28 Correct 1077 ms 7896 KB Output is correct
29 Correct 1214 ms 7928 KB Output is correct
30 Correct 1364 ms 11888 KB Output is correct
31 Correct 1211 ms 10620 KB Output is correct
32 Correct 1796 ms 32012 KB Output is correct
33 Correct 2782 ms 47220 KB Output is correct